Cod sursa(job #1302799)

Utilizator ZenusTudor Costin Razvan Zenus Data 27 decembrie 2014 12:38:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 2000007

vector < int > sol,one,two;
int lA,lB,i;
bool good[NMAX];
int inv[NMAX],H[NMAX];
char A[NMAX],B[NMAX];

vector < int > match(int base,int MOD)
{
    memset(H,0,sizeof(H));
    memset(inv,0,sizeof(inv));
    sol.clear();
    int now=0,value=0,a,i;

    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) sol.push_back(i-lA);
    }

    return sol;
}

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);

one=match(137,666013);
for (i=0;i<one.size();++i) good[one[i]]=true;

one.clear();
two=match(151,10037);
for (i=0;i<two.size();++i) if (good[two[i]]) one.push_back(two[i]);

for (i=0,printf("%d\n",one.size());i<one.size() && i<1000;++i)
printf("%d ",one[i]);

return 0;
}