Pagini recente » Cod sursa (job #1352886) | Cod sursa (job #2444452) | Cod sursa (job #676272) | Cod sursa (job #280454) | Cod sursa (job #381562)
Cod sursa(job #381562)
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
char a[MAXN],b[MAXN];
int m,n,hasha1,hasha2,p1,p2,hash1,hash2,num;
char v[MAXN];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s",a,b);
n=strlen(a);
m=strlen(b);
p1=p2=1;hasha1=hasha2=0;
for (int i=0;i<n;i++)
{
hasha1=(hasha1*P+a[i])%MOD1,hasha2=(hasha2*P+a[i])%MOD2;
if (i!=0)
p1=(p1*P)%MOD1,p2=(p2*P)%MOD2;
}
if (n>m)
{
printf("0\n");
return 0;
}
for (int i=0;i<n;i++)
hash1=(hash1*P+b[i])%MOD1,hash2=(hash2*P+b[i])%MOD2;
if (hash1==hasha1&&hash2==hasha2)
v[0]=1,num++;
for (int i=n;i<m;i++)
{
hash1=((hash1-(b[i-n]*p1)%MOD1+MOD1)*P+b[i])%MOD1,hash2=((hash2-(b[i-n]*p2)%MOD2+MOD2)*P+b[i])%MOD2;
if (hash1==hasha1 && hash2==hasha2)
v[i-n+1]=1,num++;
}
printf("%d\n",num);
num=0;
for (int i=0;i<m && num<1000;i++)
if (v[i])
num++,printf("%d ",i);
printf("\n");
return 0;
}