Cod sursa(job #956694)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 3 iunie 2013 17:46:59
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

const int N = 50005;
const int MOD = 666013;
const int LEN = 25;

int n, m;
string text;
vector <int> hash[MOD];

/*void init() {
    power[0] = 1;
    for (int i = 1; i <= LEN; ++i)
        power[i] = (power[i - 1] * BASE) % MOD;
}*/

void insert(string s) {
    int h = 0;

    for (int i = 0; i < s.size(); ++i)
        h = h * 3 + s[i] - 'a';

    hash[h % MOD].push_back(h);
}

bool exist(int x) {
    for (int i = 0; i < hash[x % MOD].size(); ++i)
        if (hash[x % MOD][i] == x)
            return true;

    return false;
}

void read() {
    f >> text;
    n = text.size();
    
    string s;
    
    while (f >> s) {
        //g << s << '\n';
        m = s.size();
        insert(s);
    }
}

void solve() {
    int sol = 0;

    if (n < m) {
        g << "0\n";
        return;
    }

    int h = 0, power = 1;
    for (int i = 0; i < m; ++i) {
        h = h * 3 + text[i] - 'a';
        if (i < m - 1)
            power *= 3;
    }

    if (exist(h))
        ++sol;

    for (int i = m; i < n; ++i) {
        h -= power * (text[i - m] - 'a');
        h = h * 3 + (text[i] - 'a');

        if (exist(h))
            ++sol;
    }

    g << sol << '\n';
}

int main() {
    //init();
    read();
    solve();
}