串的模式匹配算法之KMP算法

子串的定位操作通常称做串的模式匹配，是各种串处理系统中最重要的操作之一。

模式串T: 子串

主串S：源串

暴力法

最容易想到的就是利用回溯的思想进行暴力求解：

// O(n*m)
int getIndex(char *S, char *T) {
    int i = 0, j = 0, SLength = strlen(S), TLength = strlen(T);
    while (i < SLength && j < TLength) {
        if (S[i] == T[j]) {
            i++, j++;
        } else {
            // 回溯指针
            i = i - j + 1;
            j = 0;
        }
    }
    if(j >= TLength) return i - TLength;
    else return -1;
}

上面不足之处在于每次遇到不匹配的时候，指针总是回溯到上次的起点的下一个位置，例如下面的情况(S=ababcabcacbab T=abcac)，i=6, j =4

S:a b a b c a b c a c b a b
T:    a b c a c

按照暴力法，下次i=i - j + 1=3, j =0，但是我们经过思考，发现模式串的下标为0的元素是和下标为3的元素是相同的，那我们往后尝试匹配的过程中，只要未成功，就一定会出现下面的情况：

S:a b a b c a b c a c b a b
T:          a b c a c

那我们完全可以不同时回溯指针i和j，直接将模式串往后移动3个单位进行匹配

利用这种“部分匹配”的特性，我们可以在遇到不匹配的时候，不将指针i回溯，而是尽量将模式串往右“滑动”特定单位长度进行继续匹配。

关键是移动的长度该如何求解？

KMP算法

该算法由D.E.Knuth和V.R.Pratt和J.H.Morris同时发现的，人们称之为克努特-莫斯里-普拉特操作，简称KMP算法。该算法能将时间复杂度降到O(n+m)

该算法关键在于求解next[]，若令next[i]=j，则表示模式串中第i个字符与主串中相对应字符不匹配的时候，在模式串中需要重新和主串中该字符进行比较的字符的位置。

void getNext(char *str, int *next) {
    next[0] = 0;
    int j = 0, i = 0, length = strlen(str);
    for (i = 1; i < length; i++) {
        j = next[i - 1];
        while (j > 0 && str[j] != str[i]) {
            j = next[j - 1];
        }
        if (str[i] == str[j]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
}

int KMP(char *S, char *T) {
    int next[MAXLEN];
    getNext(T, next);
    int SLength = strlen(S), TLength = strlen(T);
    for (int i = 0, j = 0; i < SLength; i++) {
        while (j > 0 && S[i] != T[j]) {
            j = next[j - 1];
        }
        if (S[i] == T[j]) {
            j++;
        }
        if (j == TLength) {
            return i - j + 1;
        }
    }
    return -1;
}