Cod sursa(job #2482731)

Utilizator victorv88Veltan Victor victorv88 Data 28 octombrie 2019 19:51:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;



ifstream f("strmatch.in");

ofstream g("strmatch.out");



const long long mod1=100007, mod2=100021;



char sir1[2000005], sir2[2000005];

long long hash11, hash12, hash21, hash22, lungime, putere1, putere2;

long long rez[1010];

long long nr_rez, l2;



long long create_hash(char *s, long long l, long long mod)

{

    long long put=1;

    long long rez=0;

    for (long long i=l-1; i>=0; --i)

    {

        rez+=(s[i]-'A'+1)*put;

        put*=37;

        put%=mod;

        rez%=mod;

    }

    return rez;

}



long long ridicare_putere(long long x, long long putere, long long mod)

{

    long long a=x, b=1;

    while (putere)

    {

        if (putere&1)

        {

            b*=a;

            b%=mod;

        }

        a*=a;

        a%=mod;

        putere>>=1;

    }

    return b;

}



void solve()

{

    if (hash11==hash21 && hash12 == hash22)

    {

        rez[++nr_rez]=0;

    }

    long long auxh21, auxh22;

    for (long long i=1; i<l2; ++i)

    {

        auxh21=hash21-((sir2[i-1]-'A'+1)*putere1)%mod1+mod1;

        while (auxh21<0)

            auxh21+=mod1;

        auxh21%=mod1;

        auxh21*=37;

        auxh21%=mod1;

        auxh21+=(sir2[i+lungime-1]-'A'+1);





        auxh22=hash22-((sir2[i-1]-'A'+1)*putere2)%mod2;

        auxh22+=mod2;

        auxh22%=mod2;

        while (auxh22<0)

            auxh22+=mod2;

        auxh22*=37;

        auxh22%=mod2;

        auxh22+=(sir2[i+lungime-1]-'A'+1);



        hash21=auxh21;

        hash22=auxh22;

        hash21%=mod1;

        hash22%=mod2;



        if (hash11==hash21 && hash12 == hash22)

        {

            if (nr_rez<1000)

                rez[++nr_rez]=i;

            else

                ++nr_rez;

        }

    }

}


void afisare()

{
    g << nr_rez << '\n';

    int mini=min((int)nr_rez,1000);

    for (long long i=1; i<=mini; ++i)

        g  << rez[i] <<' ';

}

int main()
{
    f >> sir1 >> sir2;
    lungime=strlen(sir1);
    l2=strlen(sir2);
    for (long long i=0; i<lungime; ++i)
    {
        if (sir1[i]>='a' && sir1[i]<='z')
            sir1[i]-=32;
        if (sir1[i]>='0'&& sir1[i]<='9')
        {
            sir1[i]+=43;
        }
    }
    for (long long i=0; i<l2; ++i)
       {
           if (sir2[i]>='a' && sir2[i]<='z')
            sir2[i]-=32;
            if (sir2[i]>='0'&& sir2[i]<='9')
                sir2[i]+=43;
       }
    putere1=ridicare_putere(37,lungime-1, mod1);
    putere2=ridicare_putere(37,lungime-1, mod2);
    hash11=create_hash(sir1,lungime,mod1);
    hash12=create_hash(sir1,lungime,mod2);
    hash21=create_hash(sir2,lungime,mod1);
    hash22=create_hash(sir2,lungime,mod2);
    solve();
    afisare();
    return 0;
}