Pagini recente » Diferente pentru fmi-no-stress-4/solutii/autobuze intre reviziile 2 si 3 | Monitorul de evaluare | Statistici Kiss Gergo Kalman (Gergo28) | Monitorul de evaluare | Cod sursa (job #3232196)
#include <iostream>
#include <cstring>
#include <fstream>
#define mod1 666013
#define mod2 10003
#define baza 127
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long v1,v2,na,nb,h1,h2,i,j,p1,p2,sol[10005],nr;
char a[2000005],b[2000005];
int main()
{
fin.getline(a,2000005);
fin.getline(b,2000005);
na=strlen(a);
nb=strlen(b);
p1=p2=1;
for(i=0;i<na;i++){
h1=(h1*baza+a[i])%mod1;
h2=(h2*baza+a[i])%mod2;
if(i!=0){
p1=(p1*baza)%mod1;
p2=(p2*baza)%mod2;
}
v1=(v1*baza+b[i])%mod1;
v2=(v2*baza+b[i])%mod2;
}
if(v1==h1 && v2==h2){
sol[++j]=i-na+1;
nr++;
}
for(i=na;i<nb;++i){
v1=((v1-(b[i-na]*p1)%mod1+mod1)*baza+b[i])%mod1;
v2=((v2-(b[i-na]*p2)%mod2+mod2)*baza+b[i])%mod2;
if(v1==h1 && v2==h2){
sol[++j]=i-na+1;
nr++;
}
}
fout<<nr<<'\n';
for(i=1;i<=j;i++)fout<<sol[i]<<' ';
}