Pagini recente » Cod sursa (job #2183371) | Cod sursa (job #1526250) | Cod sursa (job #3192486) | Cod sursa (job #987529) | Cod sursa (job #317247)
Cod sursa(job #317247)
#include<string.h>
#include<stdio.h>
FILE*fin=fopen("strmatch.in","r");
FILE*fout=fopen("strmatch.out","w");
#define b 91
#define nm 2000005
#define mod1 666013
#define mod2 999017
char s[nm],t[nm];
int dim=0,ptr[nm];
int main()
{
int hash1=0,hash2=0,h1=0,h2=0,ds,dt,p1=1,p2=1,i;
fscanf(fin,"%s",&s);
fscanf(fin,"%s",&t);
ds=strlen(s);
dt=strlen(t);
for(i=0;i<ds;i++)
{
hash1=(hash1*b+s[i]);
while(hash1>=mod1) hash1-=mod1;
hash2=(hash2*b+s[i]);
while(hash2>=mod2) hash2-=mod2;
}
for(i=0;i<ds;i++)
{
h1=(h1*b+t[i]);
while(h1>=mod1) h1-=mod1;
h2=(h2*b+t[i]);
while(h2>=mod2) h2-=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]);
while(h1>=mod1) h1-=mod1;
h2=(h2*b+t[i]);
while(h2>=mod1) h2-=mod2;
if(hash1==h1&&hash2==h2)
{
dim++;
ptr[dim]=i-ds+1;
}
}
fprintf(fout,"%d\n",dim);
if(dim>1000) dim=1000;
for(i=1;i<=dim;i++)
fprintf(fout,"%d ",ptr[i]);
fclose(fin);
fclose(fout);
return 0;
}