Pagini recente » Cod sursa (job #2033503) | Cod sursa (job #3224644) | Cod sursa (job #1396351) | Cod sursa (job #158741) | Cod sursa (job #1302791)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define base 137
#define MOD 666013
#define NMAX 2000007
vector < int > sol;
int lA,lB,value,i,a,now;
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);
for (i=a=1;i<=lA;++i)
{
value=(value+a*A[i])%MOD;
a=(a*base)%MOD;
}
for (i=a=inv[0]=1,inv[1]=106951;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) sol.push_back(i-lA+1);
}
for (i=0,printf("%d\n",sol.size());i<sol.size() && i<1000;++i)
printf("%d ",sol[i]-1);
return 0;
}