Pagini recente » Cod sursa (job #1618411) | Cod sursa (job #2375625) | Cod sursa (job #2943575) | Cod sursa (job #986801) | Cod sursa (job #1943601)
#include <fstream>
#include <cstring>
#define p 73
#define mod1 100007
#define mod2 100021
#define nmax 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int hash1,hash2,i,j,na,nb;
int match[nmax];
int main()
{
int p1=1,p2=1,Ahash1=0,Ahash2=0;
f>>a;
f>>b;
na=strlen(a);
nb=strlen(b);
for(i=0;i<na;i++)
{
Ahash1=(Ahash1*p+a[i])%mod1;
Ahash2=(Ahash2*p+a[i])%mod2;
if(i)
{
p1*=p;
p2*=p;
p1%=mod1;
p2%=mod2;
}
}
if(na>nb)
g<<"0";
else
{
for(i=0;i<na;i++)
{
hash1=(hash1*p+b[i])%mod1;
hash2=(hash2*p+b[i])%mod2;
}
int nr=0;
if(hash1==Ahash1 and hash2==Ahash2)
{
nr+=1;
match[nr]=0;
}
for(i=na;i<nb;i+=1)
{
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==Ahash1 and hash2==Ahash2)
{
nr+=1;
match[nr]=i-na+1;
}
}
g<<nr<<'\n';
nr=min(nr,1000);
for(i=1;i<=nr;i++)
g<<match[i]<<" ";
}
f.close();
g.close();
return 0;
}