Pagini recente » Cod sursa (job #1276415) | Cod sursa (job #111666) | Cod sursa (job #3216656) | Cod sursa (job #2561019) | Cod sursa (job #2416129)
#include <bits/stdc++.h>
using namespace std;
const int mod1=666013,mod2=100003,base=153;
char A[2000010],B[2000010];
int ans[1010];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int hash1=0,hash2=0,p1=1,p2=1,h1=0,h2=0,sol=0,r=0;
scanf("%s\n",A+1);
scanf("%s",B+1);
int l=strlen(A+1),l1=strlen(B+1);
if(l1<l) {printf("0");return 0;}
for(int i=1;i<=l;i++)
{
hash1=(hash1*base+A[i])%mod1;
hash2=(hash2*base+A[i])%mod2;
h1=(h1*base+B[i])%mod1;
h2=(h2*base+B[i])%mod2;
if(i<l) {p1=p1*base%mod1,p2=p2*base%mod2;}
}
if(hash1==h1 && hash2==h2) {sol++;ans[++r]=0;}
for(int i=l+1;i<=l1;i++)
{
h1=((h1-(p1*B[i-l]%mod1)+mod1)*base+B[i])%mod1;
h2=((h2-(p2*B[i-l]%mod2)+mod2)*base+B[i])%mod2;
if(hash1==h1 && hash2==h2)
{
sol++;
if(r<1000) ans[++r]=i-l;
}
}
printf("%d\n",sol);
for(int i=1;i<=r;i++) printf("%d ",ans[i]);
return 0;
}