Pagini recente » Cod sursa (job #807861) | Cod sursa (job #1786051) | Cod sursa (job #2684443) | Cod sursa (job #1014878) | Cod sursa (job #2420083)
#include <cstdio>
#include <iostream>
using namespace std;
const int N=(int)2e6+7;
string s,pat;
int ps[N];
int n,m;
void buildPS()
{
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];
}
}
}
}
int ans[1007],cnt;
void KMP()
{
int i=0;
int j=0;
while(i<n)
{
if(s[i]==pat[j])
{
i++;
j++;
}
if(j==m)
{
cnt++;
if(cnt<=1000)
{
ans[cnt]=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; n=s.size(); m=pat.size();
buildPS();
KMP();
cout<<cnt<<"\n";
if(cnt>1000) cnt=1000;
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
return 0;
}