字符串匹配：KMP

基本原理

KMP核心思想与BM类似，假设主串是a，模式串是b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，找到一些规律，将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

在模式串和主串匹配的过程中，把不能匹配的那个字符叫做坏字符，把已经匹配的那段字符叫做好前缀。
当遇到坏字符的时候，把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀字符串，跟模式串的前缀子串在比较。

拿到好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配。
假设最长的可匹配的那部分前缀子串是{v}，长度是k。把模式串一次性往后滑动j-k位，相当于，每次遇到坏字符的时候，就把j更新为k，i不变，然后继续比较。
把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫做最长可匹配后缀子串；对应的前缀子串，叫做最长可匹配前缀子串。

模式串a b a b a c d
前缀子串a b a b a c

子串	前缀	后缀	最大公共元素长度	前缀结尾字符下标	最长可匹配前缀子串结尾字符下标	next值
a	空	空	0	0	-1	next[0]=-1
ab	a	b	0	1	-1	next[1]=-1
aba	a,ab	a,ba	1	2	0	next[2]=0
abab	a,ab,aba	b,ab,bab	2	3	1	next[3]=1
ababa	a,ab,aba,abab	a,ba,aba,baba	3	4	2	next[4]=2
ababac	a,ab,aba,abab,ababc	c,ac,bac,abac,babac	0	5	0	next[5]=-1

提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。把这个数组定义为next数组（失效函数）。
数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标（子字符串的前缀集合与后缀集合的交集中最长元素的长度）。

KMP算法框架

//a,b分别是主串和模式串；n,m分别是主串和模式串的长度
public static int kmp(char[] a, int n, char[] b, int m) {
    int[] next = getNext(b,m);
    int j = 0;
    for(int i = 0; i < n; ++i) {
        while(j > 0 && a[i] != b[j]) {//一直找到a[i]和b[j]
            j = next[j-1] + 1;
        }
        if(a[i] == b[j]) {
            ++j;
        }
        if(j == m) {//找到匹配模式串的了
            return i - m + 1;
        }
    }
    return -1;
}

i始终是主串的下标；j始终是模式串的下标。（i是坏字符，j是坏字符对应模式串字符的下标）
在匹配中的任何时候，主串下标为i的字符永远和模式串下标为j的字符对齐。

失效函数

按照下标从小到大，依次计算next数组的值，当要计算next[i]的时候，前面的next[0],next[1],…,next[i-1]已经计算出来了，利用已经计算出来的next值，推导next[i]的值。（动态规划的思想）

前一个b[i-1]的最长串的下一个字符与最后一个b[i]相等，那next[i]=next[i-1]+1；否则就找前一个的次长串，递归迭代这个过程，直到找到或者完全没有。

如果next[i-1]=k-1，也就是说，子串b[0,k-1]是b[0,i-1]的最长可匹配前缀子串，如果子串b[0,k-1]的下一个字符b[k]，与b[0,i-1]的下一个字符b[i]匹配，那子串b[0,k]就是b[0,i]的最长可匹配前缀子串。所以next[i]=k。

如果b[0,k-1]的下一个字符b[k]跟b[0,i-1]的下一个字符b[i]不相等。
假设b[0,i]的最长可匹配后缀子串是[r,i]。如果把最后一个字符去掉，那b[r,i-1]肯定是b[0,i-1]的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然b[0,i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于b[i]，那么就可以考察b[0,i-1]的次长可匹配后缀子串b[x,i-1]对应的可匹配前缀子串b[0,i-1-x]的下一个字符b[i-x]是否等于b[i]。如果等于，那b[x,i]就是b[0,i]的最长可匹配后缀子串。

次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串b[0,y]。查找b[0,i-1]的次长可匹配后缀子串，转化为查找b[0,y]的最长匹配后缀子串。

考察完所有的b[0,i-1]的可匹配后缀子串b[y,i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于b[i]，那这个b[y,i]就是b[0,i]的最长可匹配后缀子串。

失效函数

private static int[] getNexts(char[] b, int m) {
    int[] next = new int[m];
    next[0] = -1;
    int k = -1;
    for(int i = 1; i < m; ++i) {
        while(k != -1 && b[k+1] != b[i]) {
            k = next[k];
        }
        if(b[k+1] == b[i]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

复杂度分析

空间复杂度

KMP算法只需要一个额外的next数组，数组的大小跟模式串相同，空间复杂度为O(m)，m表示模式串的长度。

时间复杂度

KMP算法包含两部分，第一部分是构建next数组，第二部分是借助next数组匹配。

第一部分，for循环i从1开始一直增加到m，而k并不是每次for循环都会增加，所以k累计增加的值肯定小于m。而while循环里k=next[k]，实际上是在减少k的值，k累积都没有增加超过m，所以while循环里面k=next[k]总的执行次数也不可能超过m。next数组计算的时间复杂度是O(m)。

第二部分，i从0循环增长到n-1，j的增长量不可能超过i，所以肯定小于n。next[j-1]的值肯定小于j-1，所以while循环中的j=next[j-1]+1实际上也是在让j的值减少。而j总共增长的量都不会超过n，减少的量也不可能超过n，所以while循环中的这条语句总的执行次数也不会超过n。这部分的时间复杂度是O(n)。

综合两部分的时间复杂度，KMP算法的时间复杂度为O(m+n)。