Cod sursa(job #425660)
#include <stdio.h>
#define NMAX 2000005
#define P 73
#define MOD1 100007
#define MOD2 100021
#define LMAX 1005
char A[NMAX],B[NMAX];
int n,m,hash1,hash2,P1,P2,match[LMAX],r;
inline int ok(char x)
{
return (x>='A' && x<='Z') || (x>='a' && x<='z') || (x>='0' && x<='9');
}
int hash3,hash4;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A+1,NMAX,stdin);
fgets(B+1,NMAX,stdin);
while (ok(A[n+1]))
n++;
while (ok(B[m+1]))
m++;
int i;
P1=P2=1;
for (i=1; i<=n; i++)
{
hash1=(hash1*P+A[i])%MOD1;
hash2=(hash2*P+A[i])%MOD2;
if (i!=1)
P1=(P1*P)%MOD1,P2=(P2*P)%MOD2;
}
for (i=1; i<=n; i++)
{
hash3=(hash3*P+B[i])%MOD1;
hash4=(hash4*P+B[i])%MOD2;
}
if (hash1==hash3 && hash2==hash4)
match[++r]=0;
for (i=n+1; i<=m; i++)
{
hash3=((hash3-(B[i-n]*P1)%MOD1+MOD1)*P+B[i]) % MOD1;
hash4=((hash4-(B[i-n]*P2)%MOD2+MOD2)*P+B[i]) % MOD2;
if (hash1==hash3 && hash2==hash4)
{
r++;
if (r<=1000)
match[r]=i-n;
}
}
printf("%d\n",r);
for (i=1; i<=r && i<=1000; i++)
printf("%d ",match[i]);
printf("\n");
return 0;
}