题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void Next_pre(string p,vector<int> &Next)
{
for(int i=1,j=0;i<(int)p.size();i++)
{
while(j&&p[i]!=p[j]) j=Next[j-1];
if(p[i]==p[j]) j++;
Next[i]=j;
}
}
void Kmp_match(string s,string p,int begin)
{
vector<int>Next(p.length());
Next_pre(p,Next);
for(int i=begin,j=0;i<(int)s.length();i++)
{
while(j&&s[i]!=p[j]) j=Next[j-1];
if(s[i]==p[j]) j++;
if(j==p.length())
{
cout<<(i-p.length()+1)<<" ";
}
}
}
int main()
{
int n,m;
string p,s;
cin>>n>>p>>m>>s;
Kmp_match(s,p,0);
return 0;
}