Cod sursa(job #1727350)

Utilizator cristina_borzaCristina Borza cristina_borza Data 10 iulie 2016 16:44:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <algorithm>
#include <fstream>
#include <cstring>
#include <set>
#include <map>

#define MOD 1000000007

using namespace std;

char cuv[50] , prop[10000005];
int n , m , nr;

int v[50005];

bool caut_bin(int val) {
    int i , p = 0;
    for (i = 1; i <= nr; i <<= 1);
    while (i) {
        if (i + p <= nr && v[i + p] <= val) {
            p += i;
        }

        i >>= 1;
    }

    if (v[p] == val) {
        return 1;
    }

    return 0;
}

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

    scanf("%s" , &prop);
    m = strlen(prop);

    while (scanf("%s" , &cuv) != EOF) {
        int hash1 = 0;
        n = strlen(cuv);

        for (int i = 0; i < n; ++i) {
            hash1 = (hash1 * 3 + (cuv[i] - 'a')) % MOD;
        }

        v[++nr] = hash1;
    }

    sort(v + 1, v + nr + 1);

    int P1 = 1, hash1 = 0;
    for (int i = 0; i < n; ++i) {
        hash1 = (hash1 * 2 + (prop[i] - 'a')) % MOD;
        if (i) {
            P1 = (3 * P1) % MOD;
        }
    }

    if (caut_bin(hash1) == 1) {
       ++sol;
    }

    for (int i = n; i < m; ++i) {
        hash1 = ((hash1 - ((prop[i - n] - 'a') * P1) % MOD + MOD) * 3 + (prop[i] - 'a')) % MOD;

        if (caut_bin(hash1) == 1) {
            ++sol;
        }
    }

    printf("%d" , sol);
    return 0;
}