Cod sursa(job #1850087)

Utilizator SmarandaMaria Pandele Smaranda Data 18 ianuarie 2017 10:19:40
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 10000003;
const int H = 666013;
const int L = 24;

ifstream cin ("abc2.in");
ofstream cout ("abc2.out");

char s [N], d [L];
vector <long long> h [H + 2];

int main(){
    int n, i, ans = 0, l, j, k;
    bool found;
    long long a1, powBAZA;

    n = 0;
    cin.getline(s, N);
    while (1){
        cin.getline(d, L);
        if (cin.eof())
            break;
        ++n;
        l = strlen(d);
        a1 = 0;
        for (i = 0; i < l; i++)
            a1 = 1ll * a1 * 3 + d [i] - 'a';
        j = a1 % H;
        h [j].push_back (a1);
    }
    if (n == 0) {
        cout << "0\n";
        return 0;
    }
    a1 = 0;
    for (i = 0;s [i] && i < l; i++) {
        a1 = (1ll * a1 * 3 )+ s [i] - 'a';
    }
    if (i != l) {
        cout << "0\n";
        return 0;
    }

    j = a1 % H;
    found = 0;
    for (i = 0; i < h [j].size() && !found; ++i)
        if (h [j][i] == a1){
            ans++;
            found = 1;
        }

    powBAZA = 1;
    for (i = 1; i < l; i++){
        powBAZA = 1ll * powBAZA * 3;
    }

    n = strlen(s);
    for (i = 1; i <= n - l; i++){
        a1 = a1 - 1ll * (s [i - 1] - 'a') * powBAZA;
        a1 = (1ll * a1 * 3 + s [i + l - 1] - 'a');

        j = a1 % H;
        found = 0;
        for (k = 0; k < h [j].size() && !found; ++k)
            if (h [j][k] == a1){
                ans++;
                found = 1;
            }
    }
    cout << ans << "\n";
    return 0;
}