Cod sursa(job #1984578)

Utilizator victoreVictor Popa victore Data 25 mai 2017 11:28:43
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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)
{
    return c-'A';
}

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++;
    for(i=2;i<=n2-n1+1;i++)
    {
        check=(check*baza-getnum(b[i-1])*putere+getnum(b[i+n1-1]))%mod;
        check2=(check2*baza-getnum(b[i-1])*putere2+getnum(b[i+n1-1]))%mod2;
        if(check==theone&&check2==theone2)
        {
            cnt++;
            if(cnt<=1000)
                st[++top]=i-1;
        }
    }
    printf("%d\n",cnt);
    for(i=1;i<=top;i++)
        printf("%d ",st[i]);
}