Pagini recente » Cod sursa (job #559357) | Cod sursa (job #1389750) | Cod sursa (job #124408) | Cod sursa (job #2769120) | Cod sursa (job #317257)
Cod sursa(job #317257)
#include<string.h>
#include<stdio.h>
#define b 91
#define nm 2000005
#define mod1 666013
#define mod2 666649
char s[nm],t[nm];
int dim=0,ptr[nm];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int hash1=0,hash2=0,h1=0,h2=0,ds,dt,p1=1,p2=1,i;
scanf("%s",&s);
scanf("%s",&t);
ds=strlen(s);
dt=strlen(t);
for(i=0;i<ds;i++)
{
hash1=(hash1*b+s[i])%mod1;
hash2=(hash2*b+s[i])%mod2;
}
for(i=0;i<ds;i++)
{
h1=(h1*b+t[i])%mod1;
h2=(h2*b+t[i])%mod2;
}
if(hash1==h1&&hash2==h2)
{
dim++;
ptr[dim]=0;
}
for(i=1;i<ds;i++)
{
p1=(p1*b)%mod1;
p2=(p2*b)%mod2;
}
for(i=ds;i<dt;i++)
{
h1=(h1-t[i-ds]*p1)%mod1;
if(h1<0) h1+=mod1;
h2=(h2-=t[i-ds]*p2)%mod2;
if(h2<0) h2+=mod2;
h1=(h1*b+t[i])%mod1;
h2=(h2*b+t[i])%mod2;
if(hash1==h1&&hash2==h2)
{
dim++;
if(dim<=1000) ptr[dim]=i-ds+1;
}
}
printf("%d\n",dim);
if(dim>1000) dim=1000;
for(i=1;i<=dim;i++)
printf("%d ",ptr[i]);
return 0;
}