KMP算法详解

KMP匹配实际上就是在一般匹配的过程中，有没有已经匹配好的了，现场去找又太麻烦所以有了KMP

KMP数组的产生就是自己匹配自己，因为一个字符串能否接续上就是看前缀和后缀有没有重合的部分，例如：

EBDAE 这个字符串可以用 KMP 来加快匹配，因为这个字符串有这E这个共同的前缀和后缀，所以有下一个例子：

EBDAEBDAE

这个例子中，两个EBDAE叠在了一起，所以在找到第二个EBDAE时，不用重新去找，只需要在第二个E接续上就可以了。

下面是匹配的代码（此时KMP数组为空）

PS: 代码中，i代表着在i个字符范围内，可以直接接续的位置，所以真正的其实点为1，但是当只有1个字符时，最优选就是它自己，所以直接跳过。另外，因为b数组的第一个下标为0，所以里边的i要写成i-1。

// 预处理KMP
int j=0;
for(int i=2;i<=lb;i++){
    while(j && b[i-1]!=b[j]){
        j=kmp[j];
    }
    if(b[i-1]==b[j]) j++;
    kmp[i]=j;
}

以下是完整代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string a,b;
int kmp[1000002];
int main(){
    cin>>a>>b;
    int la=a.length(),lb=b.length();
    // 预处理KMP
    int j=0;
    for(int i=2;i<=lb;i++){
        while(j&&b[i-1]!=b[j]){
            j=kmp[j];
        }
        if(b[i-1]==b[j]) j++;
        kmp[i]=j;
    }
    //实践匹配
    j=0;
    for(int i=1;i<=la+1;i++){
        if(j==lb){
            j=kmp[j];
            cout<<i-lb<<endl;
        }
        // cout<<a[i-1]<<" "<<b[j]<<endl;
        while(j&&a[i-1]!=b[j]){
            j=kmp[j];
        }
        if(a[i-1]==b[j]) j++;
    }
    for(int i=1;i<=lb;i++){
        cout<<kmp[i]<<" ";
    }
    return 0;
}