Cod sursa(job #1013099)

Utilizator deneoAdrian Craciun deneo Data 20 octombrie 2013 11:59:47
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <string>
#include <set>

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

const int MOD = 67013;

string sir, a;
vector<unsigned int> v[MOD];

void insert (unsigned int code) {
    v[code % MOD].push_back(code);
}

bool find (unsigned int code) {
    for (int i = 0; i < v[code % MOD].size(); ++i)
        if (v[code % MOD][i] == code)
            return 1;
    return 0;
}

int main() {
    fin >> sir;
    int n;

    while (fin >> a) {
        unsigned int code = 0;
        n = a.size();

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

        insert(code);
    }

    unsigned int power = 1;
    for (int i = 1; i < n; ++i)
        power *= 3;

    unsigned int code = 0, rez = 0;
    for (int i = 0; i < n; ++i)
        code = code * 3 + sir[i] - 'a';

    if (find(code))
        ++rez;

    for (int i = n; i < sir.size(); ++i) {
        code -= power * (sir[i - n] - 'a');
        code = code * 3 + sir[i] - 'a';
        if (find(code))
            ++rez;
    }

    fout << rez;
    return 0;
}