Pagini recente » Cod sursa (job #573875) | Monitorul de evaluare | Cod sursa (job #2025051) | testare_chiur | Cod sursa (job #2287891)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=2000000+5;
string pat,s;
int m,n;
int ps[N];
vector<int>ans;
inline void LP()
{
ps[0]=0;
int i=1,cur=0;
while(i<m)
{
if(pat[i]==pat[cur])
{
cur++;
ps[i]=cur;
i++;
}
else
{
if(cur==0)
{
i++;
}
else
{
cur=ps[cur-1];
}
}
}
}
inline void KMP()
{
int i=0;
int j=0;
while(i<n)
{
if(s[i]==pat[j])
{
j++;
i++;
}
if(j==m)
{
ans.push_back(i-m);
j=ps[j-1];
}
if(i<n && s[i]!=pat[j])
{
if(j==0)
{
i++;
}
else
{
j=ps[j-1];
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>pat>>s;
m=pat.size();
n=s.size();
LP();
KMP();
cout<<ans.size()<<"\n";
if(ans.size()>1000)
{
ans.resize(1000);
}
for(auto &x:ans)
{
cout<<x<<" ";
}
cout<<"\n";
return 0;
}
/**
**/