Pagini recente » Cod sursa (job #1194864) | Cod sursa (job #1249060) | Cod sursa (job #1048871) | Cod sursa (job #2321640) | Cod sursa (job #1302812)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 2000007
vector < int > sol,one,two;
int lA,lB,i,j,base,MOD,a,now,value;
bool good[NMAX];
int inv[NMAX],H[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);
//FIRST HASHING
base=137,MOD=666013;
for (i=a=1;i<=lA;++i)
{
value=(value+a*A[i])%MOD;
a=(a*base)%MOD;
}
for (i=inv[1]=1;i<=MOD-2;++i)
inv[1]=(inv[1]*base)%MOD;
for (i=a=inv[0]=1;i<=lB;++i)
{
H[i]=(H[i-1]+a*B[i])%MOD;
a=(a*base)%MOD;
inv[i]=(1LL*inv[i-1]*inv[1])%MOD;
}
for (i=lA;i<=lB;++i)
{
now=(1LL*((H[i]-H[i-lA]+MOD)%MOD)*inv[i-lA])%MOD;
if (now==value) one.push_back(i-lA);
}
//SECOND HASHING
base=151,MOD=10037;
for (i=a=1,value=0;i<=lA;++i)
{
value=(value+a*A[i])%MOD;
a=(a*base)%MOD;
}
for (i=inv[1]=1;i<=MOD-2;++i)
inv[1]=(inv[1]*base)%MOD;
for (i=a=inv[0]=1;i<=lB;++i)
{
H[i]=(H[i-1]+a*B[i])%MOD;
a=(a*base)%MOD;
inv[i]=(1LL*inv[i-1]*inv[1])%MOD;
}
for (i=lA;i<=lB;++i)
{
now=(1LL*((H[i]-H[i-lA]+MOD)%MOD)*inv[i-lA])%MOD;
if (now==value) two.push_back(i-lA);
}
i=j=0;
while (i<one.size() && j<two.size())
{
if (one[i]==two[j])
{
sol.push_back(one[i]);
++i,++j;
continue;
}
(one[i]<two[j]) ? ++i : ++j;
}
for (i=0,printf("%d\n",sol.size());i<sol.size() && i<1000;++i)
printf("%d ",sol[i]);
return 0;
}