【洛谷】3375 KMP字符串匹配

【算法】KMP

【题解】【算法】字符串

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,maxm=;
char A[maxn],B[maxm];
int p[maxm],n,m;
int main()
{
scanf("%s%s",A+,B+);
n=strlen(A+);m=strlen(B+);
p[]=;
int j=;
for(int i=;i<=m;i++)
{
while(j>&&B[j+]!=B[i])j=p[j];
if(B[j+]==B[i])j++;
p[i]=j;
}
j=;
for(int i=;i<=n;i++)
{
while(j>&&B[j+]!=A[i])j=p[j];
if(B[j+]==A[i])j++;
if(j==m)
{
printf("%d\n",i-j+);
j=p[j];
}
}
for(int i=;i<m;i++)printf("%d ",p[i]);
printf("%d",p[m]);
return ;
}
上一篇:生成uid的算法


下一篇:Apache Spark 3.0 将内置支持 GPU 调度