KMP算法

北大先修课挂了……挂在了C++的字符串上，一时心血来潮学了KMP。（本文内容来自M67）

KMP是用来进行字符串匹配的算法，对于两个字符串A和B，它通过预处理B串加快匹配速度。

我们假设有A：124123678  B：123。

我们用i、j两个指针表示当前处理的A和B的字符下标。如果A[i+1]=B[j+1]，i++,j++。

如果不同怎么办呢？容易想到，对i进行操作是没有意义的。我当然要一路向后扫描A串，所以我们希望找到能匹配A[i+1]的最大的B[j+1]。

这个B[j]可以用预处理算出，记为p[j]。我们既然希望保留最大的B[j+1]，那么B[1..p[j]]应当等于B[j-p[j]+1..j]，之后i++。

我们可以发现，P数组的计算实际上就是B串的自我匹配，因此和A、B串匹配类似。

例题：codevs1204

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int p[200];

int main()
{
    string a,b;
    cin >> a >> b;
    int n=a.length(),m=b.length();
    a=" "+a; b=" "+b;
    
    int j=0;
    for(int i=2;i<=m;i++)
    {
            while (j>0 && b[j+1]!=b[i]) j=p[j];
            if (b[j+1]==b[i]) j++;
            p[i]=j;
    } 
    j=0;
    for (int i=1; i<=n; i++)
    {
        while (j>0 && a[i]!=b[j+1]) j=p[j];
        if (b[j+1]==a[i]) j++;
        if (j==m) {    cout << i-j+1 << endl; return 0; }
    }
    return 0;
}