说明

Kmp和indexOf 都是用于匹配字符串，如果匹配到目标字符串则返回首个字符下标，如果匹配到则返回-1

之前偶然打开Java String.indexOf的源码以为会很高大上，结果发现indexOf中的源码是暴力匹配字符串的…

所以准备对比一下这两个方法，不过还是先梳理一下这两个算法的源码。

KMP

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”

KMP算法流程：

1、首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词整体后移一位，因为B与A不匹配，搜索词整体再往后移

2、直到字符串有一个字符，与搜索词的第一个字符相同为止。

3、接着比较字符串和搜索词的下一个字符，一只比对到搜索词最后一个字符完成。

如果全部匹配，则返回搜索词第一个字符对应的字符串中字符的下标。(下图index)
如果某个字符不匹配，执行下一步。

kmp

4、这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

5、怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里知道如何使用即可。

6、已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

7、逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

部分匹配表（next数组）：

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例

－　"A"的前缀和后缀都为空集，共有元素的长度为0；

－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

求解Next数组

public static void cal_next(char[] str, int[] next) {
    int len = str.length;
    next[0] = -1;         //next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;           //k初始化为-1
    
    //如果下一个不同，那么k就变成next[k]，注意next[k]
    for (int q = 1; q <= len - 1; q++) {
        while (k > -1 && str[k + 1] != str[q]) { //是小于k的，无论k取任何值。
            k = next[k];                         //往前回溯
        }
        if (str[k + 1] == str[q]) {              //如果相同，k++
            k ++;
        }
        next[q] = k;      //这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
	}
}

首先我们看第一个while循环，它到底干了什么。

在此之前，我们先回到原程序。原程序里有一个大的for()循环，那这个for()循环是干嘛的？

这个for循环就是计算next[0]，next[1],…next[q]…的值。

里面最后一句next[q]=k就是说明每次循环结束，我们已经计算了ptr的前(q+1)个字母组成的子串的“相同的最长前缀和最长后缀的长度”。（这句话前面已经解释了！）这个“长度”就是k。

好，到此为止，假设循环进行到第 q 次，即已经计算了next[q]，我们是怎么计算next[q+1]呢？

比如我们已经知道ababab，q=4时，next[4]=2（k=2，表示该字符串的前5个字母组成的子串ababa存在相同的最长前缀和最长后缀的长度是3，所以k=2,next[4]=2。这个结果可以理解成我们自己观察算的，也可以理解成程序自己算的，这不是重点，重点是程序根据目前的结果怎么算next[5]的）.，那么对于字符串ababab，我们计算next[5]的时候，此时q=5, k=2（上一步循环结束后的结果）。那么我们需要比较的是str[k+1]和str[q]是否相等，其实就是str[1]和str[5]是否相等！，为啥从k+1比较呢，因为上一次循环中，我们已经保证了str[k]和str[q] (注意这个q是上次循环的q)是相等的（这句话自己想想，很容易理解），所以到本次循环，我们直接比较str[k+1]和str[q]是否相等（这个q是本次循环的q）。

如果相等，那么跳出while()，进入if()，k=k+1，接着next[q]=k。即对于ababab，我们会得出next[5]=3。这是程序自己算的，和我们观察的是一样的。

如果不等，我们可以用”ababac“描述这种情况。不等，进入while()里面，进行k=next[k]，这句话是说，在str[k + 1] != str[q]的情况下，我们往前找一个k，使str[k + 1]==str[q]，是往前一个一个找呢，还是有更快的找法呢？。程序给出了一种更快的找法，那就是 k = next[k]。程序的意思是说，一旦str[k + 1] != str[q]，即在后缀里面找不到时，我是可以直接跳过中间一段，跑到前缀里面找，next[k]就是相同的最长前缀和最长后缀的长度。所以，k=next[k]就变成，k=next[2]，即k=0。此时再比较str[0+1]和str[5]是否相等，不等，则k=next[0]=-1。跳出循环。

完整的KMP代码

public static int KMP(String s, String p) {
    int slen = s.length();
    int plen = p.length();
    char[] str = s.toCharArray();
    char[] ptr = p.toCharArray();
    int[] next = new int[plen];
    cal_next(ptr, next);
    int k = -1;
    for (int i = 0; i < slen; i++) {
        while (k > -1 && ptr[k + 1] != str[i])  //ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）
            k = next[k];                        //往前回溯
        if (ptr[k + 1] == str[i])
            k ++;
        if (k == plen - 1) {            //说明k移动到ptr的最末端
            return i - plen + 1;        //返回相应的位置
        }
    }
    return -1;
}

public static void cal_next(char[] str, int[] next) {
    int len = str.length;
    next[0] = -1;         //next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;           //k初始化为-1
    
    //如果下一个不同，那么k就变成next[k]，注意next[k]
    for (int q = 1; q <= len - 1; q++) {
        while (k > -1 && str[k + 1] != str[q]) { //是小于k的，无论k取任何值。
            k = next[k];                         //往前回溯
        }
        if (str[k + 1] == str[q]) {              //如果相同，k++
            k ++;
        }
        next[q] = k;      //这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
}

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    String full = "BBC ABCDAB ABCDABCDABDE";
    String par = "ABCDABD";
    int res = KMP(full,par);
    //int res = full.indexOf(par);
    System.out.println(res+","+(System.currentTimeMillis() - start)+"ms");
}

时间复杂度O(n)

indexOf（）

流程：

2、直到字符串有一个字符，与搜索词的第一个字符相同为止。

3、接着比较字符串和搜索词的下一个字符，一只比对到搜索词最后一个字符完成。

如果全部匹配，则返回搜索词第一个字符对应的字符串中字符的下标。
如果某个字符不匹配，执行下一步。

4、这时，和KMP不同的是，不再利用Next数组，而是将搜索词整个后移一位，再从头逐个比较。

indexOf和KMP实现同样的功能，但是用原始暴力的方法求解，所以直接来看看源码：

/**
* Code shared by String and StringBuffer to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param   source       the characters being searched.
* @param   sourceOffset offset of the source string.
* @param   sourceCount  count of the source string.
* @param   target       the characters being searched for.
* @param   targetOffset offset of the target string.
* @param   targetCount  count of the target string.
* @param   fromIndex    the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    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++) {
        /* Look for first character. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* Found first character, now look at the rest of v2 */
        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) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}

时间复杂度O(n*m)

总结：

可能是JDK的编写者们认为大多数情况下，字符串都不长，使用原始实现可能代价更低。在我测试过程中，使用indexOf方法时要比KMP算法要快一点。KMP算法对与超长字符串子匹配速度上是优于IndexOf的。

因为KMP算法需要预先计算处理来获得辅助数组，需要一定的时间和空间，这可能在短字符串查找中相比较原始实现耗费更大的代价。而且一般大字符串查找时，程序员们也会使用其它特定的数据结构，查找起来更简单。这有点类似于排除特定情况下的快速排序了。不同环境选择不同算法。

参考：经典算法-KMP

说明
1. KMP
2. indexOf（）
  1. 总结：

Java String.indexOf对比KMP

说明

KMP

KMP算法流程：

部分匹配表（next数组）：

求解Next数组

完整的KMP代码

indexOf（）

总结：

FEATURED TAGS

FRIENDS