Cod sursa(job #1302993)

Utilizator ZenusTudor Costin Razvan Zenus Data 27 decembrie 2014 15:17:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 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],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;
}