Cod sursa(job #101900)

Utilizator silviugSilviu-Ionut Ganceanu silviug Data 13 noiembrie 2007 21:49:16
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.44 kb
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

using namespace std;

#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define FOR(i, N, M) for (int i = (int)(N); i <= (int)(M); ++i)
#define FORD(i, N, M) for (int i = (int)(N); i >= (int)(M); --i)
#define FORI(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define TIP(x) (cerr << #x << " = " << (x) << endl)
#define sz size()
#define pb push_back
#define mp make_pair
#define pf first
#define ps second
#define INF 1000000000
#define ALL(x) (x).begin(), (x).end()
#define CLEAR(X) (memset(X, 0, sizeof(X)))
typedef vector<int> VI;
typedef vector<string> VS;
typedef long long LL;

const int MAX_LEN = 10000010;
const int HASH_SIZE = 1 << 20;

int N;
char cuv[64];
char text[MAX_LEN];
uint hash[HASH_SIZE];

inline uint hash_fun(uint val) {
    const uint prime = 103;
    return (val * prime) & (HASH_SIZE - 1);
}

inline void insert(uint val) {
    ++val;
    uint poz = hash_fun(val);
    for (; hash[poz]; poz = (poz + 1) & (HASH_SIZE - 1)) {
        if (hash[poz] == val) return;
    }
    hash[poz] = val;
}

inline bool find(uint val) {
    ++val;
    uint poz = hash_fun(val);
    for (; hash[poz]; poz = (poz + 1) & (HASH_SIZE - 1)) {
        if (hash[poz] == val) return true;
    }
    return false;
}

int main() {
	freopen("abc2.in", "rt", stdin);
	freopen("abc2.out", "wt", stdout);

    fgets(text, MAX_LEN, stdin);
    while (true) {
        CLEAR(cuv);
        fgets(cuv, 64, stdin);
        int len = strlen(cuv);
        if (cuv[len - 1] == '\n') {
            cuv[len - 1] = 0;
            --len;
        }
        if (len == 0) {
            break;
        }
        N = len;
        int crt = 0;
        for (int i = 0; i < len; ++i) {
            crt = crt * 3 + (cuv[i] - 'a');
        }
        insert(crt);
    }

    uint crt_hash = 0, pow3 = 1;

    for (int i = 0; i < N; ++i)
        pow3 *= 3;

    int i, sol = 0;
    for (i = 0; i < N; ++i) {
        text[i] -= 'a';
        crt_hash = crt_hash * 3 + text[i];
    }

    for (; text[i] != '\0'; ++i) {
        text[i] -= 'a';
        sol += (int) (find(crt_hash));

        crt_hash *= 3;
        crt_hash = crt_hash - pow3 * text[i - N];
        crt_hash += text[i];
    }
    printf("%d\n", sol);
	return 0;
}