Luogu 3375 【模板】KMP字符串匹配（KMP算法）
Description
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。
第一行为一个字符串，即为s1（仅包含大写字母）
第二行为一个字符串，即为s2（仅包含大写字母）
Output
若干行，每行包含一个整数，表示s2在s1中出现的位置
接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
ABABABC ABA
Sample Output
1 3 0 0 1
Http
Luogu:https://www.luogu.org/problem/show?pid=3375
Source
字符串匹配，KMP
解决思路
关于KMP算法，请参考我的这篇文章 那么要注意的是，我的这种方法求出来的Next数组（本文中用F表示）要+1才是最后要输出的结果，具体请看链接。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int maxN=1000001;
const int maxM=2001;
const int inf=2147493647;
int n,m;
string A,B;
int F[maxN];
int main()
{
cin>>A>>B;
n=A.size();;
m=B.size();
//Solve_Next
F[0]=-1;
for (int i=1;i<m;i++)
{
int j=F[i-1];
while ((B[j+1]!=B[i])&&(j>=0))
j=F[j];
if (B[j+1]==B[i])
F[i]=j+1;
else
F[i]=-1;
}
//for (int i=0;i<m;i++)
// cout<<F[i]<<' ';
//cout<<endl;
int i=0,j=0;
while (i<n)
{
if (A[i]==B[j])
{
i++;
j++;
if (j==m)
{
printf("%d\n",i-m+1);
j=F[j-1]+1;
}
}
else
{
if (j==0)
i++;
else
j=F[j-1]+1;
}
}
for (int i=0;i<m;i++)
cout<<F[i]+1<<' ';//注意这里要＋１
cout<<endl;
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7195357.html
相关资源：JAVA上百实例源码以及开源项目
