Cod sursa(job #2034814)

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

using namespace std;

int MOD1=666013;
int MOD2=666019;

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

int main()
{

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

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

    lw=strlen(w);
    ls=strlen(s);
    int rez1=0,rez2=0;
    for(int i=0;i<lw;++i)
    {
        rez1=(rez1*27+w[i]-'A'+1)%MOD1;
        rez2=(rez2*27+w[i]-'A'+1)%MOD2;
    }

    int r1=0,r2=0;
    for(int i=0;i<lw;++i)
    {
        r1=(r1*27+s[i]-'A'+1)%MOD1;
        r2=(r2*27+s[i]-'A'+1)%MOD2;
    }

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

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


    for(int i=lw;i<ls;++i)
    {
        r1-=(s[i-lw]-'A'+1)*p1;
        r2-=(s[i-lw]-'A'+1)*p2;
        if(r1<0)
            r1+=MOD1;
        if(r2<0)
            r2+=MOD2;
        r1=(r1*27+s[i]-'A'+1)%MOD1;
        r2=(r2*27+s[i]-'A'+1)%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;
}