题解 P3375 【【模板】KMP字符串匹配】
hicc0305
2018-01-21 10:17:17
###首先要说的是：千万不要用gets！！（坑死我了）###
然后，正文如下：
KMP一开始看有点晕，你先要知道的是，它是先自己和自己弄，再和大串弄。
虽然我不是P党，但这篇讲稿不错：[http://www.matrix67.com/blog/archives/115](http://www.matrix67.com/blog/archives/115)
i是a串（大串）的指针，j是b串（小串）的指针
当你匹配到j==m时，你就胜利了，此时在a串里的出现位置就是i-m+1
那么，平常的一位一位匹配，不行再i+1从头开始太慢了，明明b串前面里有和当前后面相同几位，你却又要把它重新匹配一遍。。
like：
abab***a***babe
abab***e***
啊，你发现这里炸了,因为b[1]=b[3],b[2]=b[4]你完全可以,直接这样：
ababababe
.....ababe
而不是这样：
ababababe
..ababe
于是，你想到了，可以预处理出相同的部分，怎么处理列
我们完全可以预处理出这样一个数组p[j]，表示当匹配到b数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。p[j]应该是所有满足b[1..p[j]]=b[j-p[j]+1..j]的最大值。
这样可以使得A[i-j+1..i]与B[1..j]保持匹配（此处为新的j）。
然后，下一位如果还是不能匹配，再把前一个j翻出来，再匹配一次，直到找不到相同的前缀了也就是j=0了，就只能把整个串往后挪一位了
本人可能讲的不清楚，大家看看上面那篇讲稿会好一点
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char a[1000100],b[1000100];
int p[1000100];
int main()
{
scanf("%s%s",a+1,b+1);
int la=strlen(a+1),lb=strlen(b+1);
int j=0;
p[1]=0;
//先处理出p数组，无非是b和自己匹配，与b和a匹配一样，故代码差不多
for(int i=2;i<=lb;i++)
{
while(j>0 && b[i]!=b[j+1]) j=p[j];//往前翻记录了有相同前缀的j
if(b[i]==b[j+1]) j++;//i匹配成功了，i继续往后
p[i]=j;
}
j=0;
for(int i=1;i<=la;i++)
{
while(j>0 && a[i]!=b[j+1]) j=p[j];
if(a[i]==b[j+1]) j++;
if(j==lb) printf("%d\n",i-lb+1),j=p[j];
}
for(int i=1;i<lb;i++)
printf("%d ",p[i]);
printf("%d",p[lb]);
return 0;
}
本人萌新，还请大神指教
```