Pagini recente » Cod sursa (job #2901892) | Cod sursa (job #1113033) | Cod sursa (job #2035437) | Cod sursa (job #1897259) | Cod sursa (job #381541)
Cod sursa(job #381541)
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100019
char p[MAXN],t[MAXN],n,m,v[MAXN];
int hashp,q,num,hash1,hash2,i,q1,q2;
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s",p,t);
n=strlen(p);
m=strlen(t);
q1=q2=1;
int hashp1=0,hashp2=0;
for (i=0;i<n;i++)
hashp1=(hashp1*P+p[i])%MOD1,
hashp2=(hashp2*P+p[i])%MOD2;
if (i!=0)
q1=(q1*P)%MOD1,q2=(q2*P)%MOD2;
if (n>m)
{
printf("0\n");
return 0;
}
for (i=0;i<n;i++)
hash1=(hash1*P+t[i])%MOD1,hash2=(hash1*P+t[i])%MOD2;
if (hash1==hashp1 && hash2==hashp2)
v[0]=1, num++;
for (i=n;i<m;i++)
{
hash1=((hash1-(t[i-n]*q1)%MOD1+MOD1)*P+t[i])%MOD1,
hash2=((hash1-(t[i-n]*q2)%MOD2+MOD2)*P+t[i])%MOD2;
if (hash1==hashp1&&hash2==hashp2)
v[i-n+1]=1,num++;
}
printf("%d\n",num);
num=0;
for (i=0;i<m && num<1000;i++)
if (v[i])
num++,
printf("%d ",i);
printf("\n");
return 0;
}