经典算法kmp，大神级的存在

对于字符串匹配，如用一个长度为m的模式串去匹配一个长度为n的主串，我们可以使用暴力法（BF，Brute Force），其时间复杂度为O(m*n)。

字符串匹配kmp算法的时间复杂度只需要O(m+n)。

使用变量 i, j 表示主串s[]和模式串t[]的下标， 第一轮匹配：

 

kmp算法认为，i 可以不回退（BF要求退回到主串的第2个位置（第几轮就是第几个位置）），而 j 可以回退到第2个位置，即 j=2（BF要求退回到每1个字符的位置）。

 

即使使用暴力破解，几轮迭代后，也会迭代匹配到此位置，所以上述 i，j 的回退不影响整体结果的正确性。

模式串此时回退为什么是2呢？

看下面已匹配的公共部分：

 

主串以不匹配的位置为基准，考虑前面的字符abaab，有后缀ab与模式串abaabe最前面的字符前缀ab相等。

也就是模式串本身abaab，有最大后缀部分ab与最大前缀ab相等，相等字符的长度为2。

从上图可见，假设一个字符串长度为n，其最大前缀和后缀相等的字符数量不会超过n/2，例如：

abcdabcd，长度为8，8/2=4，其最大前缀和后缀相等的字符串abcd最大可能的长度为4。

如何暴力计算下面字符的最大前缀和后缀字符串的长度L呢？

abcdaabbcdeabcd，长度n为15，其L不会超过n/2=7，暴力匹配的思路可以描述为：

前1个字符与后1个字符是否相等？

前2个字符与后2个字符是否相等？

前3个字符与后3个字符是否相等？

……

前n/2个字符与后n/2个字符是否相等？

暴力匹配的思路也可以描述为：

前n/2=7个字符与后n/2=7个字符是否相等？

abcdaabbcdeabcd

前n/2-1=6个字符与后n/2-1=6个字符是否相等？

abcdaabbcdeabcd

前n/2-2=5个字符与后n/2-2=5个字符是否相等？

abcdaabbcdeabcd

abcdaabbcdeabcd

前n/2-3=4个字符与后n/2-3=4个字符是否相等？

abcdaabbcdeabcd

此时相等，则L为4。

对于模式串abaabe，如何计算各个子串对应的最大前缀与后缀字符串数量（j回退到的位置）？

abaab	2
abaa	1
aba	1
ab	0
a	-1

图示：

 

对应代码：

int *getNextArray(char t[]) // 动态规划
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假设
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
        }
    }
    return next;
}

对于模式串T的下标 j 回退位置next[]的求解方法，KMP算法应用的动态规划的思想：

首先大胆假设next[j]=k，则

 

那么next[j+1]=?

也就是以上子串再分别多考虑一个随后的字符：

 

可以区分这两个字符在相等和不等的情况下分别考虑：

 

有了确定模式串回退位置的数组，字符串匹配剩下的代码就相对较容易了。

demo c code：

#include <stdio.h>
#include <malloc.h>
#include <string.h>
// 对主串s和模式串t进行KMP模式匹配
// 计算模式串t需要回退的位置（BF是回退到0）
int *getNextArray(char t[]) // 动态规划
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假设
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
        }
    }
    return next;
}

/**
 * 对主串s和模式串t进行KMP模式匹配
 * @param s 主串
 * @param t 模式串
 * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
 */
int kmpMatch(char* s, char* t){
    int *next = getNextArray(t);
    int i = 0, j = 0;
    while (i<(int)strlen(s) && j<(int)strlen(t)){
        if(j == -1 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    //printf("ni-j = %d - %d = %dn",i,j,i-j);
    if(j == (int)strlen(t))
        return i-j;
    else
        return -1;
}
int main()
{
    //char* str[] = {"ACBACAACAACACAACAB","ACAACAB"};
    //char* str[] = {"abaabaabeca","abaabe"};
    char* str[] = {"abaabaeabaabea","abaabe"};
    int *next = getNextArray(str[1]);
    int i,j;
    printf("主串s[]=    ");
    for(i=0;i<(int)strlen(str[0]);i++)
        printf("%c ",str[0][i]);
    printf("n");
    for(i=0;i<2;i++)
    {
        printf("模式串t[]=  ");
        for(j=0;j<(int)strlen(str[1]);j++)
            printf("%c ",str[1][j]);
        printf("n");
    }
    printf("next[]   = ");
    for(i=0;i<strlen(str[1]);i++)
        printf("%d ",next[i]);
    int n = kmpMatch(str[0],str[1]);
    printf("n模式串t首次匹配到主串s的位置：%dn",n);
    getchar();
}
/*
主串s[]=    a b a a b a a b e c a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置：3

主串s[]=    A C B A C A A C A A C A C A A C A B
模式串t[]=  A C A A C A B
模式串t[]=  A C A A C A B
next[]   = -1 0 0 1 1 2 3
模式串t首次匹配到主串s的位置：11

主串s[]=    a b a a b a e a b a a b e a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置：7

*/

demo JAVA code：

class Ideone
{
    public static int[] getNextArray(char[] t) {
        int[] next = new int[t.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for(int j = 2; j < t.length; j++) {
            k=next[j-1];
            while(k!=-1) {
                if(t[j - 1] == t[k]) {
                    next[j] = k + 1;
                    break;
                }
                else {
                    k = next[k];
                }
                next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
            }
        }
        return next;
    }
    
    /**
    * 对主串s和模式串t进行KMP模式匹配
    * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
    */
    public static int kmpMatch(String s_arr, String t_arr){
        char[] s = s_arr.toCharArray();
        char[] t = t_arr.toCharArray();
        int[] next = getNextArray(t);
        for(int i=0;i<t.length;i++)
            System.out.print(next[i] + " ");
        int i = 0, j = 0;
        while(i<s.length && j<t.length){
            if(j == -1 || s[i]==t[j]){
                i++;
                j++;
            }
            else
                j = next[j];
        }
        System.out.printf("n%d %d %dn",i,j,t.length);
        if(j == t.length)
            return i-j;
        else
            return -1;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
        int n = kmpMatch("ACBACAACAACACAACAB","ACAACAB");
        System.out.printf("%dn",n);
	}
}
/*
-1 0 0 1 1 2 3 
18 7 7
11
*/