Pagini recente » Cod sursa (job #2574679) | Cod sursa (job #2414969) | Cod sursa (job #1898050) | Cod sursa (job #2349078) | Cod sursa (job #2303073)
#include <cstdio>
#include <iostream>
using namespace std;
const int N=2000000+5;
string pat;
string s;
int m;
int n;
int pr[N];
void build()
{
pr[0]=0;
int p=1,cur=0;
while(p<m)
{
if(pat[p]==pat[cur])
{
cur++;
pr[p]=cur;
p++;
}
else
{
if(cur==0)
{
p++;
}
else
{
cur=pr[cur-1];
}
}
}
}
int cnt=0;
int ans[1234];
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=pr[j-1];
}
if(i<n && s[i]!=pat[j])
{
if(j==0)
{
i++;
}
else
{
j=pr[j-1];
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>pat>>s;
m=pat.size();
n=s.size();
build();
kmp();
cout<<cnt<<"\n";
if(cnt>1000)
{
cnt=1000;
}
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
return 0;
}