Pagini recente » Cod sursa (job #1964747) | Cod sursa (job #2540978)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX=2000004;
const int P=73;
const int mod1=100007;
const int mod2=100021;
char a[NMAX],b[NMAX],la,lb;
int amod1,bmod1,amod2,bmod2,powm1=1,powm2=1,cnt,rasp[NMAX];
int main()
{
in>>a>>b;
la=strlen(a);
lb=strlen(b);
for(int i=0;i<la;i++){
amod1=(amod1*P+a[i])%mod1;
amod2=(amod2*P+a[i])%mod2;
if(i)
powm1=(powm1*P)%mod1,
powm2=(powm2*P)%mod2;
}
if(la>lb){
out<<0;
return 0;
}
for(int i=0;i<la;i++)
bmod1=(bmod1*P+b[i])%mod1,
bmod2=(bmod2*P+b[i])%mod2;
if(amod1==bmod1 && amod2==bmod2){
rasp[cnt]=0;
cnt++;
}
for(int i=la;i<lb;i++){
bmod1=((bmod1-(b[i-la]*powm1)%mod1+mod1)*P+b[i])%mod1;
bmod2=((bmod2-(b[i-la]*powm2)%mod2+mod2)*P+b[i])%mod2;
if(amod1==bmod1 && amod2==bmod2)
rasp[cnt]=i-la+1,cnt++;
}
out<<cnt<<'\n';
for(int i=0;i<cnt && i<1000;i++)
out<<rasp[i]<<" ";
return 0;
}