String.indexOf方法和KMP算法简介

1. String.indexOf

        子字符串查找是字符串的一种基本操作:给定一段长度为 $N$ 的文本和一个长度为 $M$ 的模式 ( $pattern$ ) 字符串,在文本中找到一个和该模式相符的子字符串。对于一般的暴力式方法,在最坏的情况下运行时间与 $MN$ 成正比,但是在处理许多应用程序中的字符串时 ( 除了一些极端情况外 ),它的实际运行时间一般与 $M + N$ 成正比。另外,它很好地利用了大多数计算机系统中标准的结构特性,因此即使是更加巧妙的算法也很难超越它经过优化后的版本的性能。

public static int search(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();
    for (int i = 0; i <= N; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
        if (j == M) return i;
    }
    return N;
}

        $String.indexOf$ 提供了子字符串查找功能,实现方式也是类似于上面的暴力式方法:

/**
* String和StringBuffer共享的搜索方法,源串和模式串均由字符数组组成
*
* @param source 待搜索的串
* @param sourceOffset 源串偏移量
* @param sourceCount 源串长度
* @param target 模式串
* @param targetOffset 模式串偏移量
* @param targetCount 模式串长度
* @param fromIndex 起始搜索位置
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        chat[] target, int targetOffset, int targetCount,
        int fromIndex) {
    // 起始位置大于源串长度
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    // 起始位置小于0,设为0
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    // 模式串长度为零,返回起始位置
    if (targetCount == 0) {
        return fromIndex;
    }
    // 获取模式串第一个字符以及源字符串最大长度
    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);
    // 从偏移量开始查找
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        // 首字符不匹配,查询下一个匹配位置
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        if (i <= max) {
            // 第二个字符位置
            int j = i + 1;
            // 剩余待匹配长度
            int end = j + targetCount - 1;
            // 匹配剩余串
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);
            // 匹配成功,返回起始索引
            if (j == end) {
                return i - sourceOffset;
            }
        }
    }
    // 匹配失败,返回-1
    return -1;
}

2. KMP

        KMP算法的基本思想是当出现不匹配时,就能知晓一部分文本的内容 ( 因为在匹配失败之前它们已经和模式相匹配 )。我们可以利用这些信息避免将指针回退到所有这些已知的字符之前。例如对于字符串 $ABCDABD$ ,当我们匹配到倒数第一个字符即 $B$ 的时候,如果发现不匹配,我们没有必要再将模式指针移到开头,而是移到第三个字符即 $C$ ,因为我们已经知道了前面两个字符必定为 $AB$ 。
        为了实现上述回退操作,我们需要实现一个 $next[\ ]$ 数组记录回退位置。我们可以将字符串分为前缀和后缀两个部分,每个字符都有对应的前缀和后缀,例如对于 $ABAB$ ,有:

索引 $0$ $1$ $2$ $3$
前缀 $A$ $AB$ $ABA$
后缀 $BAB$ $AB$ $B$

        而构造的 $next[\ ]$ 数组记录的就是除当前字符外最长的相同前缀后缀。简单的来讲就是对于每个从 $0$ 开始的子串,寻找其前缀后缀集合中最长的公有元素。再以 $ABAB$ 为例:

        获取了最长公有元素长度后,就可以构造 $next[\ ]$ 数组了,构造的时候只需要将首位设为 $-1$ ,然后将求得的数字统一右移一格即可。

模式串 $A$ $B$ $A$ $B$
数组 $-1$ $0$ $0$ $1$

        但是显然,对于每个 $index[i]$ ,如果每次都要计算前缀和后缀,然后比较统计长度,那么花费的时间可能会比暴力搜索要久。我们可以利用动态规划的思想,利用先前求得的值。例如对于 $ABCDABCE$ ,我们已经计算出前 $7$ 位值如下:

模式串 $A$ $B$ $C$ $D$ $A$ $B$ $C$
最长前后缀公有串长度 $0$ $0$ $0$ $0$ $1$ $2$ $3$
$next$ $-1$ $0$ $0$ $0$ $0$ $1$ $2$

        此时对于第 $j = 8$ 位 $E$ ,可以发现有 $pattern[j - 1] == pattern[next[j - 1]]$ ,也就意味着第 $j - 1$ 个子串的前后缀最长公有元素的长度必定为第 $j - 2$ 个子串的长度加 $1$ ,也即 $index[j] = index[j - 1] + 1$ 。
        而对于不相等的情况如 $ABCDABDE$ ,有:

模式串 $A$ $B$ $C$ $D$ $A$ $B$ $D$
最长前后缀公有串长度 $0$ $0$ $0$ $0$ $1$ $2$ $0$
$next$ $-1$ $0$ $0$ $0$ $0$ $1$ $2$

        这时再对第 $j = 8$ 位 $E$ 比较,可以发现 $pattern[j - 1] != pattern[next[j - 1]]$ 。这时就需要递归索引,即令 $k = next[j - 1]$ ,然后再比较 $pattern[j - 1]$ 与 $pattern[next[k]]$ ,直到 $k == -1$ 或者 $pattern[j - 1] == pattern[next[k]]$ ,对于后者,我们就令 $next[j] == next[k] + 1$。因为相同前缀的子串在模式串中可能多次出现,之前的 $next$ 值记录的可能是靠后的前缀子串的位置,所以我们需要递归查找直到所有相同前缀子串遍历完成。
        从而KMP算法的实现为:

public class KMP {
    public static int search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();
        int[] next = getNext(pat, N);
        int i = 0, j = 0;
        while (i < M && j < N) {
            if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else j = next[j];
        }
        return j == N ? i - j : -1;
    }

    private static int[] getNext(String pat, int N) {
        int[] next = new int[N];
        next[0] = -1;
        int k = -1, j = 0;
        while (j < N - 1) {
            if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
                k++;
                j++;
                next[j] = k;
            } else k = next[k];
        }
        return next;
    }
}

        至此已经完成了KMP算法,但是还存在着一个问题,举个例子,对于字符串 $ABACABABC$ 和模式串 $ABAB$ ,可以得出 $next[\ ] = \{-1, 0, 0, 1\}$ 。然后进行匹配,直到第 $4$ 个字符,此时 $txt[3] = “C”$ ,$pat[3] = “B”$ ,于是 $txt[3] != pat[3]$ ,查找得出 $j = next[3] = 1$ ,于是又重新比对 $txt[3]$ 和 $pat[1]$ 。显然最后一步是没有必要的,因为我们已经知道 $txt[3] != “B”$ 了。所以我们可以对原来的 $next[\ ]$ 数组进行优化:

public static int[] getNextVal(String pat, int N) {
    int[] nextVal = new int[N];
    nextVal[0] = -1;
    int k = -1, j = 0;
    while (j < N - 1) {
        if (k == -1 || pat.charAt(j) == pat.chatAt(k)) {
            j++;
            k++;
            if (pat.charAt(j) != pat.charAt(k)) nextVal[j] = k;
            else nextVal[j] = nextVal[k];
        } else k = nextVal[k];
    }
    return nextVal;
}

        实现思路很简单,就是在每次递增后判断当前字符是否与 $next$ 值相等,如果相等,就递归 $next$ 值。

String.indexOf方法和KMP算法简介