Pagini recente » Cod sursa (job #223265) | Cod sursa (job #554528) | Cod sursa (job #3160161) | Cod sursa (job #471202) | Cod sursa (job #1098923)
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, i, t, p1, p2, x, ap1, ap2, bp1, bp2, v[2000009];
int pprim1[100030], pprim2[100030];
char a[2000009], b[2000009];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a);
gets(b);
n=strlen(a);
m=strlen(b);
if(n>m) {printf("0");return 0;}
p2=100007;
p1=100021;
pprim1[0]=1;
pprim2[0]=1;
for(i=1;i<=90009;i++)
{
pprim1[i]=(pprim1[i-1]*73)%p1;
pprim2[i]=(pprim2[i-1]*73)%p2;
}
x=0;
for(i=n-1;i>=0;i--)
{
ap1=(ap1+(a[i])*pprim1[x])%p1;
ap2=(ap2+(a[i])*pprim2[x])%p2;
bp1=(bp1+(b[i])*pprim1[x])%p1;
bp2=(bp2+(b[i])*pprim2[x])%p2;
x++;
}
x--;
t=0;
if(ap1==bp1&&ap2==bp2)
{
t++;
v[t]=0;
}
for(i=1;i<=m-n;i++)
{
bp1=((bp1-(b[i-1]*pprim1[x])%p1+p1)*73+b[i+n-1])%p1;
bp2=((bp2-(b[i-1]*pprim2[x])%p2+p2)*73+b[i+n-1])%p2;
if(ap1==bp1&&ap2==bp2)
{
t++;
v[t]=i;
}
}
printf("%d\n", t);
if(t>1000) t=1000;
for(i=1;i<=t;i++)
printf("%d ", v[i]);
return 0;
}