Cod sursa(job #1984586)

Utilizator victoreVictor Popa victore Data 25 mai 2017 12:05:46
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
#include<cstring>
#include<cmath>

const int nmax=2000005;
const int mod=666013;
const int mod2=326323;
const int baza=103;

char a[nmax],b[nmax];

int st[1005],top=0;

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

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int putere=1,theone=0,n,i,j,check=0,cnt=0,n1,n2,check2=0,theone2=0,putere2=1;
    gets(a+1);
    gets(b+1);
    n1=strlen(a+1);
    n2=strlen(b+1);
    if(n1>n2)
    {
        printf("0");
        return 0;
    }
    for(i=1;i<=n1;i++)
    {
        check=((check*baza)+getnum(b[i]))%mod;
        check2=((check2*baza)+getnum(b[i]))%mod2;
        theone=((theone*baza)+getnum(a[i]))%mod;
        theone2=((theone2*baza)+getnum(a[i]))%mod2;
        putere=putere*baza%mod;
        putere2=putere2*baza%mod2;
    }
    if(check==theone)
    {
        cnt++;
        st[++top]=0;
    }
    for(i=n1+1;i<=n2;i++)
    {
        check=(check*baza-(getnum(b[i-n1])*putere)%mod+getnum(b[i]))%mod;
        check2=(check2*baza-(getnum(b[i-n1])*putere2)%mod2+getnum(b[i]))%mod2;
        if(check==theone&&check2==theone2)
        {
            cnt++;
            if(cnt<=1000)
                st[++top]=i-n1;
        }
    }
    printf("%d\n",cnt);
    for(i=1;i<=top;i++)
        printf("%d ",st[i]);
}