北大先修课挂了……挂在了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
     
      #include
      
       #include
       
        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;}