KMP字符串匹配
解题思路
这题就是kmp的模板题
百度百科的解释
巨爷myc的“深入浅出”
kmp就是一个时间复杂度为O(n+m)的处理字符串匹配问题的算法
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,len1,len2,next[1000005];
string s1,s2;
void getnext()//求next数组
{
for(int i=1,k=0;i<len2;i++)//定义两个变量
{
while(k&&s2[i]!=s2[k]) k=next[k-1];//不相等
if(s2[i]==s2[k]) k++;//相等
next[i]=k;//赋值
}
}
void kmp()
{
next[0]=0;//初值
getnext();
for(int i=0,k=0;i<len1;i++)//下面同上面神似
{
while(k&&s1[i]!=s2[k]) k=next[k-1];
if(s1[i]==s2[k]) k++;
if(k==len2)
printf("%d\n",i-len2+2);
}
}
int main()
{
cin>>s1;//输入
cin>>s2;
len1=s1.size();
len2=s2.size();
kmp();
for(int i=0;i<len2;i++)//输出
printf("%d ",next[i]);
return 0;
}