题解 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;
}
本人萌新,还请大神指教
```