Pagini recente » Cod sursa (job #445469) | Rating Chita Catalin Adrian (daytarel) | Cod sursa (job #1057155) | Cod sursa (job #482645) | Cod sursa (job #2786972)
#include <bits/stdc++.h>
using namespace std;
const int Mod1=666013;
const int Mod2=10003;
const int p=109;
char a[2000005],b[2000005];
int rez[2000005],nr;
long long h1,h2,v1,v2,putere1,putere2;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.sync_with_stdio(false);
cin.tie(0);
cin>>a>>b;
int m=strlen(a);
int n=strlen(b);
h1=h2=a[0]-'0'+1;
putere1=putere2=1;
for(int i=1; i<m; ++i)
{
h1=(h1*p+a[i]-'0'+1)%Mod1;
h2=(h2*p+a[i]-'0'+1)%Mod2;
putere1=(putere1*p)%Mod1;
putere2=(putere2*p)%Mod2;
}
for(int i=0; i<m; ++i)
{
v1=(v1*p+b[i]-'0'+1)%Mod1;
v2=(v2*p+b[i]-'0'+1)%Mod2;
}
if(v1==h1 && v2==h2)
{
rez[++nr]=0;
}
for(int i=m; i<n; ++i)
{
v1=(1LL*(v1-(1LL*putere1*(b[i-m]-'0'+1))%Mod1+Mod1)*p+b[i]-'0'+1)%Mod1;
v2=(1LL*(v2-(1LL*putere2*(b[i-m]-'0'+1))%Mod2+Mod2)*p+b[i]-'0'+1)%Mod2;
if(v1==h1 && v2==h2)
{
rez[++nr]=i-m+1;
}
}
cout<<nr<<'\n';
for(int i=1; i<=nr && i<=1000; ++i)
{
cout<<rez[i]<<' ';
}
return 0;
}