Pagini recente » Cod sursa (job #2601747) | Cod sursa (job #2592793) | Cod sursa (job #2030652) | Cod sursa (job #1597122) | Cod sursa (job #381533)
Cod sursa(job #381533)
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD 100007
char p[MAXN],t[MAXN],n,m,v[MAXN];
int hashp,q,num,hash,i;
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s",p,t);
n=strlen(p);
m=strlen(t);
q=1;
hashp=0;
for (i=0;i<n;i++)
{
hashp=(hashp*P+p[i])%MOD;
if (i!=0)
q=(q*P)%MOD;
}
if (n>m)
{
printf("0\n");
return 0;
}
for (i=0;i<n;i++)
hash=(hash*P+t[i])%MOD;
if (hash==hashp)
v[0]=1, num++;
for (i=n;i<m;i++)
{
hash=((hash-(t[i-n]*q)%MOD+MOD)*P+t[i])%MOD;
if (hash==hashp)
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;
}