Cod sursa(job #565448)

Utilizator nandoLicker Nandor nando Data 27 martie 2011 19:37:42
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define MAXN 10000010
#define MAXW 21
#define MOD1 666013
#define MOD2 666019
#define SIGMA 24

FILE* fin = fopen ("abc2.in", "r");
FILE* fout = fopen ("abc.out", "w");

vector<int> hash [MOD1];
char buf[MAXN], str[MAXW];
int len, n;

typedef vector <int>::iterator iter;

inline void add (int key1, int key2)
{
    for (iter it = hash[key1].begin (); it != hash[key1].end (); ++it) {
        if (*it == key2) {
            return;
        }
    }
    hash[key1].push_back (key2);
}

inline bool getHash (int key1, int key2)
{
    for (iter it = hash[key1].begin (); it != hash[key1].end (); ++it) {
        if (*it == key2) {
            return true;
        }
    }
    return false;
}

inline void process ()
{
    int key1 = 0, key2 = 0;
    for (int i = 0; i < len; ++i) {
        key1 = (key1 * SIGMA + str[i]) % MOD1;
        key2 = (key2 * SIGMA + str[i]) % MOD2;
    }
    add (key1, key2);
}

int main ()
{
    fgets (buf, MAXN, fin);

    fgets (str, MAXW, fin);
    len = strlen (str) - 1;
    n = strlen (buf) - 1;

    process ();

    while (!feof (fin) && fgets (str, MAXW, fin)) {
        process ();
    }

    int h1 = 1, h2 = 1, p1 = 0, p2 = 0;
    for (int i = 0; i < len; ++i) {
        p1 = (SIGMA * p1 + buf[i]) % MOD1;
        p2 = (SIGMA * p2 + buf[i]) % MOD2;

        if (i != 0) {
            h1 = (h1 * SIGMA) % MOD1;
            h2 = (h2 * SIGMA) % MOD2;
        }
    }

    int match = 0;
    for (int i = 0; i <= n - len; ++i) {
        match += getHash (p1, p2);

        if (i < n - len) {
            p1 = ((p1 - (buf[i] * h1) % MOD1 + MOD1) * SIGMA + buf[i + len]) % MOD1;
            p2 = ((p2 - (buf[i] * h2) % MOD2 + MOD2) * SIGMA + buf[i + len]) % MOD2;
        }
    }

    fprintf (fout, "%d\n", match);

    fclose (fin);
    fclose (fout);
    return 0;
}