Cod sursa(job #2262641)

Utilizator calinfloreaCalin Florea calinflorea Data 17 octombrie 2018 17:41:35
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
#define P 50000 + 3
#define NMax 10000000 + 7
using namespace std;

ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
vector <int> Hash[P];
char a[NMax], s[27];
int pow3[25];
int n, cod, cnt;
inline void Citire ()
{
    fin >> a;

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

    while (fin >> s)
    {
        n = strlen (s);
        for (int i = 0; i < n; i++)
            cod += pow3[i] * (s[i] - 'a');
        Hash[cod % P].push_back(cod);
        cod = 0;
    }
    cod = 0;

}

inline void Rezolva ()
{
    int M;
    ///primul cuvant
    for (int i = 0; i < n; i++)
        cod += pow3[i] * (a[i] - 'a');
    int X = cod % P;
    for (auto w : Hash[X])
    {
        if (cod == w)
        {
            cnt++;
            break;
        }
    }

    ///restul sirului

    M = strlen (a);
    for (int i = n; i < M; i++)
    {
        cod /= 3;
        cod += pow3[n - 1] * (a[i] - 'a');
        X = cod % P;
        for (auto w : Hash[X])
        {
            if (w == cod)
            {
                cnt++;
                break;
            }
        }
    }

    fout << cnt << "\n";
}
int main()
{
    Citire();
    Rezolva();
    return 0;
}