Pagini recente » Cod sursa (job #3215424) | Cod sursa (job #1230375) | Cod sursa (job #2289804) | Cod sursa (job #889729) | Cod sursa (job #1098924)
#include<cstdio>
#include<cstring>
using namespace std;
#define m1 100007
#define m2 100021
int n,m,i,a1,a2,k,p1,p2,b1,b2,c[2000001];
char a[2000001],b[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a)-1;
m=strlen(b)-1;
if(n>m)
{
printf("0");
return 0;
}
for(i=0;i<=n;i++)
{
a1=(a1*73+a[i])%m1;
a2=(a2*73+a[i])%m2;
}
p1=1;
p2=1;
for(i=0;i<=n;i++)
{
b1=(b1*73+b[i])%m1;
b2=(b2*73+b[i])%m2;
if(i>0)
{
p1=(p1*73)%m1;
p2=(p2*73)%m2;
}
}
if(a1==b1&&a2==b2)k++,c[k]=0;
for(i=n+1;i<=m;i++)
{
b1=((b1-(b[i-n-1]*p1)%m1+m1)*73+b[i])%m1;
b2=((b2-(b[i-n-1]*p2)%m2+m2)*73+b[i])%m2;
if(a1==b1&&a2==b2)k++,c[k]=i-n;
}
printf("%d\n",k);
if(k>1000)k=1000;
for(i=1;i<=k;i++)
printf("%d ",c[i]);
return 0;
}