Pagini recente » Cod sursa (job #2328399) | Cod sursa (job #2784144) | Cod sursa (job #1139204) | Cod sursa (job #709435) | Cod sursa (job #2786967)
#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';
putere1=putere2=1;
for(int i=1; i<m; ++i)
{
h1=(h1*p+a[i]-'0')%Mod1;
h2=(h2*p+a[i]-'0')%Mod2;
putere1=(putere1*p)%Mod1;
putere2=(putere2*p)%Mod2;
}
for(int i=0; i<m; ++i)
{
v1=(v1*p+b[i]-'0')%Mod1;
v2=(v2*p+b[i]-'0')%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'))%Mod1+Mod1)*p+b[i]-'0')%Mod1;
v2=(1LL*(v2-(1LL*putere2*(b[i-m]-'0'))%Mod2+Mod2)*p+b[i]-'0')%Mod2;
if(v1==h1 && v2==h2)
{
rez[++nr]=i-m+1;
}
}
cout<<nr<<'\n';
for(int i=1; i<=nr; ++i)
{
cout<<rez[i]<<' ';
}
return 0;
}