Cod sursa(job #2488577)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 7 noiembrie 2019 09:24:03
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int MAXS = 1e7 + 10, MAXN = 5e4 + 10, MAXLEN = 25, MOD = 666013, BASE = 4;
char matrix[MAXN][MAXLEN], input[MAXS];
int hash1[MAXN], n, m, h, power = 1;

void read() {
    fin.getline(input, MAXS);
    while (fin.getline(matrix[n++], MAXLEN));
}

void preprocess() {
    --n;
    m = strlen(matrix[0]);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            hash1[i] = (hash1[i] * BASE + (matrix[i][j] - 'a' + 1)) % MOD;
    }
    for (int i = 0; i < m; ++i) {
        h = (h * BASE + (input[i] - 'a' + 1)) % MOD;
        if (i)
            power = (power * BASE) % MOD;
    }
}

int findPos() {
    int pos = 0;
    if (binary_search(hash1, hash1 + n, h))
        ++pos;
    for (int i = m; input[i]; ++i) {
        h = ((h - ((input[i - m] - 'a' + 1) * power) % MOD + MOD) * BASE + input[i] - 'a' + 1) % MOD;
        if (binary_search(hash1, hash1 + n, h))
            ++pos;
    }
    return pos;
}

int main() {
    read();
    preprocess();
    sort(hash1, hash1 + n);
    fout << findPos();
    return 0;
}