Cod sursa(job #1302825)

Utilizator ZenusTudor Costin Razvan Zenus Data 27 decembrie 2014 13:03:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#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];
}

for (i=lA;i<=lB;++i)
{
    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;
}