Cod sursa(job #1502139)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 14 octombrie 2015 11:16:01
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#include <vector>
#include <cstring>

#define MOD 90907

using namespace std;

char s[10000010];
char word[21];

vector<unsigned int> table[MOD];

int search_table(unsigned int hash) {
    unsigned int n = table[hash % MOD].size();
    for(unsigned int i = 0; i < n; i++)
        if(table[hash % MOD][i] == hash)
            return 1;
    return 0;
}

void add_to_table(unsigned int hash) {
    if (!search_table(hash))
        table[hash % MOD].push_back(hash);
}

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

    scanf("%s", s);
    unsigned int i = 0;
    unsigned int hash = 0;
    unsigned int len;
    while(!feof(stdin)) {
        scanf("%s", word);
        len = strlen(word);
        hash = 0;
        for(i = 0; i < len; i++)
            hash = (hash * 3 + word[i] - 'a');
        add_to_table(hash);
    }
    unsigned int sol = 0;
    unsigned int offset = 1;
    hash = 0;
    for(i = 0; i < len; i++) {
        hash = hash * 3 + s[i] - 'a';
        offset *= 3;
    }
    offset /= 3;

    sol += search_table(hash);
    unsigned int slen = strlen(s);

    for(i = len; i < slen; i++) {
        hash = (hash - offset * (s[i - len] - 'a')) * 3 + s[i] - 'a';
        sol += search_table(hash);
    }
    printf("%ld\n", sol);
    return 0;
}