Pagini recente » Istoria paginii utilizator/emilia.ciobanu | Cod sursa (job #1821169) | Cod sursa (job #1344105) | Rating deniz ozguluk (silver89976) | Cod sursa (job #1120262)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int nmax = 2000005;
const int mod1 = 100009;
const int mod2 = 100003;
const int base = 104;
int n,m,i,q,sol[nmax],cnt,a1,a2,b1,b2,B1,B2;
char a[nmax],b[nmax];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a+1); n=strlen(a+1);
scanf("%s",b+1); m=strlen(b+1);
for(i=1;i<=n;i++)
{
a1=(a1*base+a[i])%mod1;
a2=(a2*base+a[i])%mod2;
}
B1=B2=1;
for(i=1;i<n;i++)
{
B1=(B1*base)%mod1;
B2=(B2*base)%mod2;
}
for(i=1;i<=n;i++)
{
b1=(b1*base+b[i])%mod1;
b2=(b2*base+b[i])%mod2;
}
if(a1==b1 && a2==b2) sol[++cnt]=1;
for(;i<=m;i++)
{
b1=((b1-(B1*b[i-n])%mod1+mod1)*base+b[i])%mod1;
b2=((b2-(B2*b[i-n])%mod2+mod2)*base+b[i])%mod2;
if(a1==b1 && a2==b2)
if(++cnt<=1000) sol[cnt]=i-n;
}
printf("%d\n",cnt);
for(i=1;i<=min(1000,cnt);i++) printf("%d ",sol[i]);
return 0;
}