字符串匹配——KMP

题目

  查找字符串 s2 在字符串 s1 的位置，如果存在则返回起始下标，不存在则返回 -1。

暴力破解

  我们使用指针的方式对字符串的每个字符进行比较。

/**
 * 暴力破解
 *
 * @param s s为被匹配字符串 babababcbabababb
 * @param p p为匹配字符串   bababb
 */
private static int indexOf(String s, String p) {
    // i 指针指向s字符串，即匹配字符串的起始下标
    int i = 0;
    // sc 指针指向s字符串
    int sc = i;
    // j 指针指向p字符串
    int j = 0;
    // 当 sc 指向 s 的末尾时结束循环
    while (sc < s.length()) {
        // 如果 sc 和 j 指向字符串的字符相同，则指针向后移动
        if (s.charAt(sc) == p.charAt(j)) {
            sc++;
            j++;
            // 当指针 j 指向 p 字符串末尾时，表示字符串匹配，结束方法
            if (j == p.length()) {
                return i;
            }
        } else {
            // 如果不相同，则移动i指针，其他指针恢复默认值
            i++;
            sc = i;
            j = 0;
        }
    }
    return -1;
}

KMP

  所谓 KMP 就是在指针暴力破解的基础上，引入 next 数组，来确定每次 j 指针回溯的位置（而不是每次都回溯到 0），从而提高效率。

next 数组

  next 数组中储存的是字符串中前缀和后缀相同字符串的最长长度，在字符匹配时，失配后其中的值决定指针回退的位置。

求 next 数组的方法

  求字符串的 next 数组方法，先将字符串拆分成字节数组 p ，并定义 j 指针指向 next 数组的下标（指向 下标 1，0 下标为 -1），然后定义 k 指针指向最长匹配前缀的下标（默认为 0）。如果 p[j]==p[k] 或 k<0，则 next(++j)=++k ；否则，k 回溯（k = next[k]），直到 j < length - 1。
  我们可以确定 next 数组的第一个元素值为 -1，因而可以得到第二个元素值为 0，后面的根据公式进行推导。假如：s 字符串为 babababcbabababb，p 字符串为 bababb。首先列出 p 字符串的所有前缀，如图：（next[3] 存储的是 bab 前缀和后缀相同字符串的最长长度，所以为 1，依次类推）

  求 next 数组的代码实现：

private static int[] next(String ps) {
    int length = ps.length();
    int[] next = new int[length];
    char[] p = ps.toCharArray();
    next[0] = -1;
    if (ps.length() == 1) {
        return next;
    }
    next[1] = 0;
    int j = 1;
    // 确定位置j的最长匹配前缀在那哪里
    int k = next[j];
    while (j < length - 1) {
        // 现在要推出next[j+1]，检查j和k位置上的关系即可
        if (k < 0 || p[j] == p[k]) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    return next;
}

KMP 的代码实现

  在指针暴力破解的基础上，引入 next 数组，来确定每次 j 指针回溯的位置，时间复杂度为 O(n+m)。

private static int indexOf(String s, String p) {
    // i 指向s字符串
    int i = 0;
    // j 为指向p字符串
    int j = 0;
    // 求得 next 数组
    int[] next = next(p);
    // 当 i 指向 s 的末尾时结束循环
    while (i < s.length()) {
        // 如果 i 和 j 指向字符串的字符相同，则指针向后移动
        if (j == -1 || s.charAt(i) == p.charAt(j)) {
            i++;
            j++;
        } else {
            // j 根据 next 数组回溯到指定下标
            j = next[j];
        }
        // 当指针 j 指向 p 字符串末尾时，表示字符串匹配，结束方法
        if (j == p.length()) {
            return i-j;
        }
    }
    return -1;
}