Pagini recente » Cod sursa (job #852583) | Cod sursa (job #765575) | Cod sursa (job #2096431) | Cod sursa (job #2986859) | Cod sursa (job #2075717)
#include <bits/stdc++.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
bool V[2000005];
int na,nb;
int main()
{ fin>>a>>b;
na=strlen(a);
nb=strlen(b);
int p1=1,p2=1,hA1=0,hA2=0;
for(int i=0;i<na;++i)
{
hA1=( hA1*P+a[i])%MOD1;
hA2=(hA2*P+a[i])%MOD2;
if(i!=0)
{p1=(p1*P)%MOD1;
p2=(p2*P)%MOD2;
}
}
if(na>nb)
{fout<<0; return 0;}
int hB1=0,hB2=0;
for(int i=0;i<na;++i)
{ hB1=(hB1*P+b[i])%MOD1;
hB2=(hB2*P+b[i])%MOD2;
}
int Nr=0;
if(hA1==hB1 && hA2==hB2)
V[0]=1,Nr++;
// fout<<hA1<<" "<<hA2<<" "<<hB1<<" "<<hB2<<"\n";
for(int i=na;i<nb;++i)
{ hB1=((hB1-(b[i-na]*p1)%MOD1 +MOD1 )*P+ b[i])%MOD1;
hB2=((hB2-(b[i-na]*p2)%MOD2 +MOD2 )*P+ b[i])%MOD2;
if(hA1==hB1 && hA2==hB2)
V[i-na+1]=1,++Nr;
// fout<<hA1<<" "<<hA2<<" "<<hB1<<" "<<hB2<<"\n";
}
fout<<Nr<<"\n";
Nr=0;
for(int i=0;i<nb && Nr<1000;++i)
if(V[i])
++Nr,fout<<i<<" ";
return 0;
}