Cod sursa(job #1849646)

Utilizator SmarandaMaria Pandele Smaranda Data 17 ianuarie 2017 18:54:09
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <queue>
#include <unordered_set>

using namespace std;

const int N = 10000003;
const int H = 666013;
const int BAZA = 3;

char s [N];
char d [50003][22];
unordered_set <int> h;
unordered_set <int> :: iterator it;

int main(){
    int n, i, k, a1, ans, powBAZA, l, j;

    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    n = 0;
    scanf("%s\n", s);
    while ((scanf("%s", d [++ n]) != EOF));

    if (n == 1) {
        printf("0\n");
        return 0;
    }
    l = strlen(d [1]);
    for (i = 1; i <= n; i++) {
        a1 = 0;
        for (j = 0; j < l; j++) {
            a1 = (1ll * a1 * BAZA % H + d [i][j] - 'a') % H;
        }
        it = h.find(a1);
        if (it != h.end()) {
            continue;
        }
        h.insert(a1);
    }

    a1 = 0;
    for (i = 0;s [i] && i < l; i++) {
        a1 = (1ll * a1 * BAZA % H + s [i] - 'a') % H;
    }
    if (i != l) {
        printf("0\n");
        return 0;
    }
    ans = 0;
    it = h.find(a1);
    if (it != h.end())
        ans++;

    powBAZA = 1;
    for (i = 1; i < l; i++){
        powBAZA = powBAZA * BAZA % H;
    }

    n = strlen(s);
    for (i = 1; i < n - l; i++){
        a1 = ((a1 - ((s [i - 1] - 'a') * powBAZA)% H) + H) % H;
        a1 = (a1 * BAZA % H + s [i + l - 1] - 'a') % H;
        it = h.find(a1);
        if (it != h.end())
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}