Pagini recente » Cod sursa (job #1341614) | Cod sursa (job #2887090) | Cod sursa (job #1528953) | Cod sursa (job #1826967) | Cod sursa (job #1302993)
#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],code;
const int MOD[]={666013,10037};
const int base[]={137,151};
int inv[2][NMAX],H[2][NMAX];
char A[NMAX],B[NMAX];
inline int root(int value,int MOD)
{
if (value<0) return value+MOD;
if (value>=MOD) return value-MOD;
return value;
}
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[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)
{
if (i<=lA)
{
value[j]=value[j]+a[j]*A[i];
while (value[j]>=MOD[j]) value[j]-=MOD[j];
}
H[j][i]=H[j][i-1]+a[j]*B[i];
while (H[j][i]>=MOD[j]) H[j][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)
{
code=H[j][i]-H[j][i-lA];
if (code<0) code+=MOD[j];
now[j]=(1LL*code*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;
}