Pagini recente » Cod sursa (job #830009) | Cod sursa (job #678375) | Cod sursa (job #279512) | Cod sursa (job #2849375) | Cod sursa (job #402875)
Cod sursa(job #402875)
#include<stdio.h>
#include<string.h>
char sb[2000010],s[2000010];
int p=73,mod1=100007,mod2=100021,h1sb,h2sb,h1s,h2s,n,nb,i,q,nr,v[10000],p1=1,p2=1;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&sb,&s);
nb=strlen(sb);
n=strlen(s);
if(nb>n)
{
printf("0\n");
return 0;
}
for(i=0;i<nb;i++)
{
h1sb=(h1sb*p+sb[i])%mod1;
h2sb=(h2sb*p+sb[i])%mod2;
if(i)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
for(i=0;i<n;i++)
{
if(i<nb)
{
h1s=(h1s*p+s[i])%mod1;
h2s=(h2s*p+s[i])%mod2;
}
else
{
h1s=((h1s-(s[i-nb]*p1)%mod1+mod1)*p+s[i])%mod1;
h2s=((h2s-(s[i-nb]*p2)%mod2+mod2)*p+s[i])%mod2;
}
if(h1sb==h1s&&h2sb==h2s)
{
nr++;
if(q<10000)
v[q++]=i-nb+1;
}
}
printf("%d\n",nr);
for(i=0;i<q;i++)
printf("%d ",v[i]);
return 0;
}