Cod sursa(job #2482758)

Utilizator victorv88Veltan Victor victorv88 Data 28 octombrie 2019 20:24:48
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

const int mod1=100007, mod2=100021;

char sir[10000005], cuvant[25];

int hash1[50005], hash2[50005], ind, l, putere1=4, putere2=4, rez, hashcuv1, hashcuv2;

bool fr1[100010], fr[100010];

int create_hash(char *s, int l, int mod)
{
    int sum=0;
    int p=1;
    for (int i=l-1; i>=0; --i)
    {
        sum=sum+(s[i]-'a'+1)*p;
        p*=4;
        p%=mod;
        sum%=mod;
    }
    return sum;
}

void create_putere()
{
    for (int i=2; i<l; ++i)
    {
        putere1*=4;
        putere1%=mod1;
        putere2*=4;
        putere2%=mod2;
    }
}

void solve()
{
    hashcuv1=create_hash(sir, l, mod1);
    hashcuv2=create_hash(sir, l, mod2);
    for (int i=1; i<=ind; ++i)
    {
        if (hashcuv1==hash1[i] && hashcuv2==hash2[i])
            rez++;
    }
    int lungime=strlen(sir);
    int dif=lungime-l;
    int auxhash1, auxhash2;
    for (int i=1; i<=dif; ++i)
    {
        auxhash1=hashcuv1-(sir[i-1]-'a'+1)*putere1;
        auxhash1%=mod1;
        auxhash1*=4;
        auxhash1+=(sir[i+l-1]-'a'+1);
        auxhash1%=mod1;

        auxhash2=hashcuv2-(sir[i-1]-'a'+1)*putere2;
        auxhash2%=mod2;
        auxhash2*=4;
        auxhash2+=(sir[i+l-1]-'a'+1);
        auxhash2%=mod2;

        hashcuv1=auxhash1;
        hashcuv2=auxhash2;

        for (int j=1; j<=ind; ++j)
        {
            if (hashcuv1==hash1[j] && hashcuv2==hash2[j])
                rez++;
        }
    }
    g << rez;
}

int main()
{
    int ah1, ah2;
    f >> sir;
    while (f>>cuvant)
    {
        if (ind==0)
            l=strlen(cuvant);
        ah1=create_hash(cuvant, l, mod1);
        ah2=create_hash(cuvant, l, mod2);
        if (fr[ah1]==0 || fr[ah2]==0)
        {
            hash1[++ind]=ah1;
            hash2[ind]=ah2;
            fr[ah1]=true;
            fr[ah2]=true;
        }

    }
    create_putere();
    solve();
    return 0;
}