Cod sursa(job #961172)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 18:18:23
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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 <unsigned 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) {
    unsigned 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(unsigned 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;
    }
 
    unsigned 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();
}