Pagini recente » Cod sursa (job #351369) | Cod sursa (job #289944) | Diferente pentru documentatie/textile intre reviziile 107 si 27 | Cod sursa (job #1352617) | Cod sursa (job #402866)
Cod sursa(job #402866)
#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 min(int a, int b)
{
if(a<b)return a;
return b;
}
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=1;i<=nb-1;i++)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
for(i=0;i<nb;i++)
{
h1sb=(h1sb*p+sb[i])%mod1;
h2sb=(h2sb*p+sb[i])%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++;
v[q++]=i-nb+1;
}
}
printf("%d\n",nr);
int t=min(q,10000)
for(i=0;i<t;i++)
printf("%d ",v[i]);
return 0;
}