KMP算法———模板

做出KMP字符串匹配算法心情也是好好哒,萌萌哒。

感谢黄学长,感谢栋栋!

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int p[101];
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&&b[j+1]!=a[i])j=p[j];
if(b[j+1]==a[i])j++;
if(j==m){printf("%d",i-m+1);break;}
}
return 0;
}

原文地址:https://www.cnblogs.com/xiaoqi7/p/5224275.html