Pagini recente » Diferente pentru home intre reviziile 903 si 320 | Diferente pentru home intre reviziile 903 si 593 | Cod sursa (job #1518903) | Diferente pentru home intre reviziile 903 si 565 | Cod sursa (job #1518659)
#include <cstdio>
#include <cstring>
#define B 123
#define MOD1 1000007
#define MOD2 1000021
#define N 2000000
char s1[N], s2[N];
int v[N];
int main()
{
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
int n1,n2,i,x1=0,x2=0,y1=0,y2=0,put1=1,put2=1,cate;
scanf("%s%s" , s1, s2);
n1=strlen(s1);
n2=strlen(s2);
if(n1>n2)
printf("0");
else
{
for(i=0; i<n1; i++)
{
x1=((x1*B)+s1[i])%MOD1;
x2=((x2*B)+s1[i])%MOD2;
y1=((y1*B)+s2[i])%MOD1;
y2=((y2*B)+s2[i])%MOD2;
if(i>=1)
{
put1=(put1*B)%MOD1;
put2=(put2*B)%MOD2;
}
}
cate=0;
if(x1==y1 && x2==y2)
{
cate++;
v[cate]=0;
}
for(i=n1; i<=n2; i++)
{
y1=(((((y1-s2[i-n1]*put1)%MOD1)*B)%MOD1)+s2[i])%MOD1;
y2=(((((y2-s2[i-n1]*put2)%MOD2)*B)%MOD2)+s2[i])%MOD2;
if(x1==y1 && x2==y2)
{
cate++;
if(cate<=1000)
v[cate]=i-n1+1;
}
}
if(cate>1000)
cate=1000;
printf("%d\n" , cate);
for(i=1; i<=cate; i++)
printf("%d ", v[i]);
}
return 0;
}