Cod sursa(job #1984589)

Utilizator victoreVictor Popa victore Data 25 mai 2017 12:41:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<cstdio>
#include<cstring>

const int mod1=666013;
const int mod2=1165823;
const int baza=63;
const int nmax=2000005;

char a[nmax],b[nmax];
int st[1005];

inline int getnum(char ch)
{
    if(ch>='0'&&ch<='9')
        return ch-'0'+1;
    if(ch>='a'&&ch<='z')
        return ch-'a'+11;
    return ch-'A'+37;
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int na,nb;
    gets(a);
    gets(b);
    na=strlen(a);
    nb=strlen(b);
    int i,hasha1,hasha2,hashb1,hashb2,putere1,putere2;
    hasha1=hasha2=hashb1=hashb2=0;
    putere1=putere2=1;
    for(i=0;i<na;i++)
    {
        hasha1=(hasha1*baza+getnum(a[i]))%mod1;
        hashb1=(hashb1*baza+getnum(b[i]))%mod1;
        hasha2=(hasha2*baza+getnum(a[i]))%mod2;
        hashb2=(hashb2*baza+getnum(b[i]))%mod2;
        if(i!=0)
        {
            putere1=putere1*baza%mod1;
            putere2=putere2*baza%mod2;
        }
    }
    int cnt=0;
    if(hasha1==hashb1&&hasha2==hashb2)
        st[++cnt]=0;
    for(i=na;i<nb;i++)
    {
        hashb1=(((hashb1-(getnum(b[i-na])*putere1)%mod1+mod1)%mod1)*baza+getnum(b[i]))%mod1;
        hashb2=(((hashb2-(getnum(b[i-na])*putere2)%mod2)%mod2+mod2)*baza+getnum(b[i]))%mod2;
        if(hasha1==hashb1&&hasha2==hashb2)
        {
            cnt++;
            if(cnt<=1000)
                st[cnt]=i-na+1;
        }
    }
    printf("%d\n",cnt);
    for(i=1;i<=cnt&&i<=1000;i++)
        printf("%d ",st[i]);
}