Cod sursa(job #2901432)

Utilizator stefanchpStefan Chiper stefanchp Data 13 mai 2022 18:35:26
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>
#include <unordered_map>
#define mod 666013
using namespace std;

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

vector <pair <long long, int>> v[666013];
string text, aux;

long long conversie(string s, long long p)
{
    long long nrb3 = 0;
    int lg = s.size();
    for (int i = 0; i < lg; i++)
        nrb3 += (s[i] - 'a') * p, p /= 3;
    return nrb3;
}

int main()
{
    long long nrb3 = 0;
    long long p = 1, p2;

    fin >> text;
    fin >> aux;
    int lg = aux.size();
    for (int i = 1; i < lg; i++)
        p *= 3;
    p2 = p;
    for (int i = 0; i < lg; i++)
        nrb3 += (text[i]-'a') * p, p /= 3;
    v[nrb3 % mod].push_back({ nrb3,1 });
    bool ok;
    for (int i = 1; i < text.size() - lg + 1; i++)
    {
        nrb3 = (nrb3 - (text[i - 1] - 'a') * p2) * 3 + (text[i + lg - 1] - 'a');
        ok = 0;
        for (int j = 0; j < v[nrb3 % mod].size(); j++)
            if (v[nrb3 % mod][j].first == nrb3)
            {
                ok = 1;
                v[nrb3 % mod][j].second++;
                break;
            }
        if (ok == 0) v[nrb3 % mod].push_back({ nrb3,1 });
    }
    long long sol = 0;
    long long aux1;
    aux1 = conversie(aux, p2); 
    ok = 0;
    for (int j = 0; j < v[aux1 % mod].size(); j++)
        if (v[aux1 % mod][j].first == aux1)
        {
            ok = 1;
            sol += v[aux1 % mod][j].second;
            v[aux1 % mod][j].first = -1;
            break;
        }
    while (fin >> aux)
    {
        aux1 = conversie(aux, p2);
        for (int j = 0; j < v[aux1 % mod].size(); j++)
            if (v[aux1 % mod][j].first == aux1)
            {
                ok = 1;
                sol += v[aux1 % mod][j].second;
                v[aux1 % mod][j].first = -1;
                break;
            }
    }
    fin.close();
    fout<<sol;
    fout.close();
    return 0;
}