Cod sursa(job #530473)

Utilizator darrenRares Buhai darren Data 7 februarie 2011 20:58:45
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

const int MOD = 3033;
vector<unsigned int> Hash[MOD];

void Add(unsigned int value)
{
    int pos = value % MOD;
    for (vector<unsigned int>::iterator it = Hash[pos].begin(); it != Hash[pos].end(); ++it)
        if (*it == value)
            return;
    Hash[pos].push_back(value);
}
bool Find(unsigned int value)
{
    int pos = value % MOD;
    for (vector<unsigned int>::iterator it = Hash[pos].begin(); it != Hash[pos].end(); ++it)
        if (*it == value)
            return true;
    return false;
}

int N, M;
char text[10000002], query[22];
int result;

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

    fin.getline(text, sizeof(text));
    N = strlen(text);

    while (fin.getline(query, sizeof(query)))
    {
        if (!M) M = strlen(query);

        unsigned int now = 0;
        for (int i = 0; query[i] != '\0'; ++i)
            now *= 3, now += query[i] - 'a';

        Add(now);
    }

    long long pow3 = 1;
    for (int i = 1; i <= M; ++i)
        pow3 *= 3;

    long long pnow = 0;
    for (int i = 0; i < M; ++i)
        pnow *= 3, pnow += text[i] - 'a';

    result += Find(pnow);
    for (int i = M; i < N; ++i)
    {
        pnow *= 3, pnow %= pow3, pnow += text[i] - 'a';
        result += Find(pnow);
    }

    fout << result;

    fin.close();
    fout.close();
}