Pagini recente » Cod sursa (job #1137367) | Cod sursa (job #2153808) | Cod sursa (job #3005518) | Cod sursa (job #1958033) | Cod sursa (job #1302954)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 2000007
vector < int > sol;
int lA,lB,i,j,a[2],now[2],value[2];
const int MOD[]={666013,10037};
const int base[]={137,151};
int inv[2][NMAX],H[2][NMAX];
char A[NMAX],B[NMAX];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",(A+1),(B+1));
lA=strlen(A+1),lB=strlen(B+1);
for (i=a[1]=a[0]=1;i<=lA;++i)
for (j=0;j<=1;++j)
{
value[j]=(value[j]+a[j]*A[i])%MOD[j];
a[j]=(a[j]*base[j])%MOD[j];
}
for (i=a[0]=a[1]=inv[0][0]=inv[1][0]=1,inv[0][1]=106951,inv[1][1]=1130;i<=lB;++i)
{
for (j=0;j<=1;++j)
{
H[j][i]=(H[j][i-1]+a[j]*B[i])%MOD[j];
a[j]=(a[j]*base[j])%MOD[j];
inv[j][i]=(1LL*inv[j][i-1]*inv[j][1])%MOD[j];
}
if (i>=lA)
{
for (j=0;j<=1;++j)
now[j]=(1LL*((H[j][i]-H[j][i-lA]+MOD[j])%MOD[j])*inv[j][i-lA])%MOD[j];
if (now[0]==value[0] && now[1]==value[1]) sol.push_back(i-lA);
}
}
for (i=0,printf("%d\n",sol.size());i<sol.size() && i<1000;++i)
printf("%d ",sol[i]);
return 0;
}