Cod sursa(job #978899)

Utilizator a96tudorAvram Tudor a96tudor Data 30 iulie 2013 12:29:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include<cstdio>
#include<cstring>

#define B1 101
#define B2 109

#define MOD1 10013
#define MOD2 666013

using namespace std;

char s[2000010];
int v[2000010];

int VAL1,VAL2,P1,P2,NR1,NR2,i,n,nr,m;


//verificarea valorilor

inline bool verif ()
{
    if ((VAL1==NR1) && (VAL2==NR2)) return true;
                    else return false;
}

//calcularea puterilor

inline void GenPutere(int n, int &nr1,int &nr2)
{
    int a=B1,b=B2,p=n,i;
    for (i = 0; (1<<i) <= p; i++)
    {
        if ( ((1<<i) & p) > 0)
                {
                    nr1= (nr1 * a) % MOD1;
                    nr2= (nr2 * b) % MOD2;
                }
        a=(a *a) %MOD1;
        b=(b*b) %MOD2;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(s);
    nr=0;
    n=strlen(s);

    //precalculare valori - primul sir

    for (i=0;i<n;i++)
    {
        P1=1;
        P2=1;
        GenPutere(n-i-1,P1,P2);
        VAL1+=((s[i])*P1)%MOD1;
        VAL1%=MOD1;
        VAL2+=((s[i])*P2)%MOD2;
        VAL2%=MOD2;
    }

    gets(s);
    m=strlen(s);

    //precalculare valori - al doilea sir

    for (i=0;i<n;i++)
    {
        P1=1;
        P2=1;
        GenPutere(n-i-1,P1,P2);
        NR1+=((s[i])*P1)%MOD1;
        NR1%=MOD1;
        NR2+=((s[i])*P2)%MOD2;
        NR2%=MOD2;
    }

    if (verif())
        {
            nr++;
            v[nr]=0;
        }

    //calculare valori - al doilea sir -
    P1=1;
    P2=1;
    GenPutere(n-1,P1,P2);
    for (i=n;i<m;i++)
    {
        NR1=(((NR1-s[i-n]*P1) % MOD1 + MOD1) * B1 + s[i]) % MOD1;
        NR2=(((NR2-s[i-n]*P2) % MOD2 + MOD2) * B2 + s[i]) % MOD2;
        if (verif())
        {
            nr++;
            v[nr]=i-n+1;
        }
    }
    printf("%d\n",nr);
    for (i=1;i<=nr;i++)
        printf("%d ",v[i]);
    printf("\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}