字符串匹配KMP算法

假设我们的字符串母串是，子串是，我们想找到子串在母串中出现的位置并统计总的出现次数，可以使用KMP算法。KMP算法需要先求解失配函数，失配函数的意义如下：的最长公共前后缀是（的最长公共前后缀是的含义是k是最大的满足且的非负整数）。

求失配函数需要用到全局变量：

const int MAXW = 10000+5;
char W[MAXW]; // 子串
int nex[MAXW]; // 失配函数，即next(i)=nex[i]

求失配函数的代码如下：

nex[0] = -1; // 特殊规定nex[0]的值为-1
int i, j;
for(i=0;W[i];i++){
    // 根据nex[i]的值求nex[i+1]的值
    // nex[i]=0表示不存在最长公共前后缀
    j = nex[i];
    while(j>=0 && W[j]!=W[i]) j = nex[j];
    nex[i+1] = j+1;
}

但实际上失配函数还有可以优化的地方，对于的最长公共前后缀，假如，则在处失配时必定也将继续在处失配，故可以改进失配函数。改进失配函数的含义如下：是的最长的满足的公共前后缀。

求改进失配函数的代码如下：

nex[0] = -1; // 特殊规定nex[0]的值为-1
int i, j;
for(i=0,j=-1;W[i];i++){
    // 根据nex[i]的值求nex[i+1]的值
    // nex[i]=0表示不存在最长公共前后缀
    // 此时j等于未改进时的失配函数nex[i]
    while(j>=0 && W[j]!=W[i]) j = nex[j];
    nex[i+1] = W[i+1]==W[++j] ? nex[j] : j;
}

求好了失配函数之后，便可以利用失配函数进行字符串匹配了。需要用到的全局变量：

const int MAXT = 1000000+5;
const int MAXW = 10000+5;
char T[MAXT], W[MAXW]; // T是母串，W是子串
int nex[MAXW]; // 之前求出的失配函数

KMP算法利用失配数组进行字符串匹配的具体代码如下：

int i, j, ans = 0; // ans表示W在T中出现的次数
for(i=j=0;T[i];i++){
    // 此时已经匹配到了W[j-1]和T[i-1]
    while(j>=0 && W[j]!=T[i]) j = nex[j];
    if(!W[++j]) ans++;
}

---

附上一道KMP模板题：POJ3461 Oulipo。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXW = 10000+5;
const int MAXT = 1000000+5;
int nex[MAXW];
char W[MAXW], T[MAXT];
int main(){
    int TC; scanf("%d", &TC);
    while(TC--){
        scanf("%s%s", W, T);
        memset(nex, 0, sizeof(nex));
        nex[0] = -1;
        int i, j, ans = 0;
        for(i=0,j=-1;W[i];i++){
            while(j>=0 && W[j]!=W[i]) j = nex[j];
            nex[i+1] = W[i+1]==W[++j] ? nex[j] : j;
        }
        for(i=j=0;T[i];i++){
            while(j>=0 && W[j]!=T[i]) j = nex[j];
            if(!W[++j]) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}