Cod sursa(job #2263044)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 18 octombrie 2018 07:02:41
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <bits/stdc++.h>
#define P 30031

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

vector <long long> H[P];
char textAntic[10000005], s[24];
int n, sol;
long long codare;
long long p3[23];


void Citire()
{
    fin >> textAntic;

    p3[0] = 1;
    for(int i = 1; i <= 21; i++)
        p3[i] = 3 * p3[i - 1];

    while(fin >> s)
    {
        n = strlen(s);

        for(int i = 0; i < n; i++)
            codare += (p3[i] * (s[i] - 'a'));

        int r = codare % P;
        H[r].push_back(codare);

        codare = 0;
    }
}

void Rez()
{
    int N, r;

    ///Primul cuvant
    for(int i = 0; i < n; i++)
        codare += p3[i] * (textAntic[i] - 'a');

    N = strlen(textAntic);

    ///Toate celelalte cuvinte (secvente)
    /// codare / 3 elimina prima litera. Adaugam ulterior urmatoarea litera
    /// avansand cu secventa
    for(int i = n; i < N; i++)
    {
        r = codare % P;
        for(auto w : H[r])
        {
            if(w == codare)
            {
                sol++;
                break;
            }
        }

        codare /= 3;
        codare += p3[n - 1] * (textAntic[i] - 'a');
    }

    ///Ultimul cuvant
    r = codare % P;
    for(auto w : H[r])
    {
        if(w == codare)
        {
            sol++;
            break;
        }
    }

    fout << sol << " ";
}

int main()
{
    Citire();
    Rez();
    return 0;
}