Cod sursa(job #1302791)

Utilizator ZenusTudor Costin Razvan Zenus Data 27 decembrie 2014 12:26:25
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#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;
}