Cod sursa(job #2482366)

Utilizator altcontnoualt cont altcontnou Data 28 octombrie 2019 10:26:08
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 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*=27;
        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*=27;
        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*=27;
        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;
    }
    for (long long i=0; i<l2; ++i)
        if (sir2[i]>='a' && sir2[i]<='z')
            sir2[i]-=32;
    putere1=ridicare_putere(27,lungime-1, mod1);
    putere2=ridicare_putere(27,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;
}