Cod sursa(job #2034833)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 8 octombrie 2017 15:02:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cstring>

using namespace std;

int MOD1=666013;
int MOD2=666019;

char s[2000005];
char w[2000005];
int sol[2000005];
int cod[5000];

int main()
{

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int nrsol=0,lw,ls;

    scanf("%s%s",&w,&s);

    for(int i=0;i<26;++i)
    {
        cod['a'+i]=i+1;
        cod['A'+i]=i+26+1;
        if(i<=10)
            cod['0'+i]=i+26+26+1;
    }

    lw=strlen(w);
    ls=strlen(s);
    int rez1=0,rez2=0;
    for(int i=0;i<lw;++i)
    {
        rez1=(rez1*63+cod[w[i]])%MOD1;
        rez2=(rez2*63+cod[w[i]])%MOD2;
    }

    int r1=0,r2=0;
    for(int i=0;i<lw;++i)
    {
        r1=(r1*63+cod[s[i]])%MOD1;
        r2=(r2*63+cod[s[i]])%MOD2;
    }

    if(r1==rez1&&r2==rez2)
    {
        sol[++nrsol]=0;
    }

    int p1=1,p2=1;
    for(int i=1;i<lw;++i){
        p1=p1*63%MOD1;
        p2=p2*63%MOD2;
    }


    for(int i=lw;i<ls;++i)
    {
        r1-=(cod[s[i-lw]])*p1;
        r2-=(cod[s[i-lw]])*p2;
        if(r1<0)
            r1+=MOD1;
        if(r2<0)
            r2+=MOD2;
        r1=(r1*63+cod[s[i]])%MOD1;
        r2=(r2*63+cod[s[i]])%MOD2;
        if(r1==rez1&&r2==rez2)
        {
            sol[++nrsol]=i-lw+1;
        }
    }

    printf("%d\n",nrsol);
    for(int i=1;i<=nrsol;++i)
        printf("%d ",sol[i]);

    return 0;
}