题目描述
服了,之前刚会过,又给忘记了。
还有对next到底求的的是什么不太清楚。
是求当前0~i对应的还是0~i-1的。还是两个都对,一个需要减去什么。
https://www.cnblogs.com/aninock/p/13796006.html
对应图解,理解为什么j++就可以
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include <string>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m;
int ne[N];
char p[N],s[M];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
//next数组,总是j+1和i比较
//比较的为模板串
for(int i=2,j=0;i<=n;i++)
{
while(j>0&&p[i]!=p[j+1])j=ne[j];
if(p[i]==p[j+1])j++;
ne[i]=j;
//cout<<ne[i];
}
//匹配和求next类似,再最后加上判断j指针是否与要求的模板串一样长。
for(int i=1,j=0;i<=m;i++)
{
while(j>0&&s[i]!=p[j+1])j=ne[j];
if(s[i]==p[j+1])j++;
if(j==n)
{
cout<<i-n<<" ";
j=ne[j];
}
}
}
`