Pagini recente » Cod sursa (job #346965) | Cod sursa (job #2034338) | Cod sursa (job #2203564) | Cod sursa (job #8966) | Cod sursa (job #565864)
Cod sursa(job #565864)
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;
fstream f1,f2;
char a[2000002],b[2000002],match[2000002];
int na,nb,i,p1,p2,p,mod1,mod2,nr1,hasha1,hasha2,hash1,hash2;
int main()
{
p=73;
mod1=1007;
mod2=1021;
f1.open("strmatch.in",ios::in);
f2.open("strmatch.out",ios::out);
f1>>a>>b;
na=strlen(a);
nb=strlen(b);
if(na>nb)
cout<<"0";
p1=p2=1;
hasha1=hasha2=0;
for(i=0;i<na;i++)
{
hasha1=(hasha1*p+a[i])%mod1;
hasha2=(hasha2*p+a[i])%mod2;
if(i!=0)
{
p1=p1*p%mod1;
p2=p2*p%mod2;
}
}
hash1=hash2=0;
for(i=0;i<na;i++)
{
hash1=(hash1*p+b[i])%mod1;
hash2=(hash2*p+b[i])%mod2;
}
nr1=0;
if(hash1==hasha1&&hash2==hasha2)
{
match[0]=1;
nr1++;
}
for(i=na;i<nb;i++)
{
hash1=((hash1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
hash2=((hash2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
if(hash1==hasha1&&hash2==hasha2)
{
match[i-na+1]=1;
nr1++;
}
}
cout<<nr1<<"\n";
nr1=0;
for(i=0;i<nb&&nr1<1000;i++)
if(match[i])
cout<<i<<" ";
f1.close();
f2.close();
return 0;
}