Pagini recente » Cod sursa (job #1437992) | Cod sursa (job #1777187) | Cod sursa (job #357867) | Cod sursa (job #3124069) | Cod sursa (job #574985)
Cod sursa(job #574985)
#include<stdio.h>
#include<string.h>
#define b 73
#define mod1 100007
#define mod2 100021
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int n,i,j,p1,p2,h1,h2,ha1,ha2,nr,x,y,sol[1001];
char v[2000001],w[2000001];
int main() {
fscanf(f,"%s\n",v);
fscanf(f,"%s",w);
x=strlen(v);
y=strlen(w);
for(i=0;i<x;++i){
ha1=(ha1*b+v[i])%mod1;
ha2=(ha2*b+v[i])%mod2;
}
for(i=0;i<x;++i){
h1=(h1*b+w[i])%mod1;
h2=(h2*b+w[i])%mod2;
}
if(h1==ha1&&h2==ha2)
sol[++nr]=0;
p1=p2=1;
for(i=1;i<x;++i){
p1=p1*b%mod1;
p2=p2*b%mod2;
}
for(i=x;i<y;++i){
h1=((h1-(w[i-x]*p1)%mod1+mod1)*b+w[i])%mod1;
h2=((h2-(w[i-x]*p2)%mod2+mod2)*b+w[i])%mod2;
if(h1==ha1&&h2==ha2)
if(nr<1000)
sol[++nr]=i-x+1;
else
++nr;
}
fprintf(g,"%d\n",nr);
if(nr>1000)
nr=1000;
for(i=1;i<=nr;++i)
fprintf(g,"%d ",sol[i]);
fclose(g);
fclose(f);
return 0;
}