字符串搜索子串的算法（KMP算法）

菲洛

比如在字符串s:"a a a b"中搜索t:"a a b",

在比较s[2]!=t[2]后，下一次直接比较s[2]和t[1]是否相等，而不是从

s[1]和t[0]开始比较。即我们在第一次匹配中有部分信息有可能加

速我们的第二次匹配，第二次匹配没必要从t[0]开始比较。我们创

建一个长度为t.length的整数数组next，对于t中的每一个字符t[i]，

next[i]表示字符t[i]之前有没有可以加速匹配的信息。具体表示是：

（注意上面的max里面i-k是大于0的）

next[i]字面意思是t[i]前面最多有k（k<t.length）个元素与从头开始

的k个元素相等，所以当s[j]!=t[i]时，接着直接让s[j]与t[next[i]]作比

较（因为下标是从0开始，不是1），如果直到next[i]=-1,依然不相等，那么就比较s[j+1]与t[0]（最坏情况）

获取next数组的办法:

public void getNext(String str,int[]next) {
        int j,k;
        j=0;k=-1;next[0]=-1;
        int len=str.length();
        while(j<len-1) {
            if(k==-1||str.charAt(j)==str.charAt(k)) {
                ++j;++k;
                next[j]=k;
            }
            else k=next[k]; /*这里也是利用
            前面得到的next数组来加速循环过程*/
        }
    }

实际应用:题目

 public int strStr(String haystack, String needle) {
            int len=needle.length();
            int[]next=new int[len];
            if(len==0)
                 return 0;
            getNext(needle,next);
            int i=0,j=0,len2=haystack.length();
            while(i<len2) {
                if(j==-1||haystack.charAt(i)==needle.charAt(j)) {
                    ++j;
                    ++i;
                    if(j==len) {
                        return i-len;
                    }
                }
                else {
                    j=next[j];
                }
            }
            return -1;
        }

时间复杂度：
设s长度为n, t的长度为m。
则 求next数组复杂度为O(m),因为在匹配过程中s的下标不会减少，比较次数是n，这个算法的平均时间复杂度为O(n+m)。
最坏的时间复杂度为O(n x m)。

到现在还没看懂的话，原谅我的理解和表达能力，可以先放下，

过段时间再去思考。