Cod sursa(job #758460)

Utilizator AndreyPAndrei Poenaru AndreyP Data 15 iunie 2012 18:58:44
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.14 kb
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <iostream>
#include <fstream>
#include <utility>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int, int >
#define pdd pair< double, double >

template< typename T >
inline T minim(const T x, const T y) {
    return ((x < y) ? x : y);
}
template< typename T >
inline T maxim(const T x, const T y) {
    return ((x > y) ? x : y);
}

#define NA 26       // dimensiune alfabet
#define LA 1000010  // lungime sir A
#define LW 10010    // lungime cuvant
#define N 110       // nr de cuvinte


struct Node {
    Node* son[NA];
    vector< int > words;
    int nr;
    Node* fail;

    Node() {
        memset(son, 0, sizeof(son));
        nr = 0;
    }
};

char a[LA];
int n;
Node* T;
vector< Node* > q;
int rez[N];

void ins(Node* node, char const* p, const int& i) {
    int nSon;

    if (*p == '\0') {
        node -> words.pb(i);
        return;
    }

    nSon = int(*p - 'a');
    if (node -> son[nSon] == NULL) {
        node -> son[nSon] = new Node;
    }

    ins(node -> son[nSon], p + 1, i);
}

inline void bfs() {
    Node* now;
    Node* next;
    Node* node;

    q.pb(T);
    T -> fail = T;

    for (size_t i = 0; i < q.size(); ++i) {
        now = q[i];

        for (int j = 0; j < NA; ++j) {
            if (now -> son[j] == NULL) {
                continue;
            }

            next = now -> son[j];
            for (node = now -> fail; node != T && node -> son[j] == NULL; node = node -> fail) {
                ;
            }

            if (node -> son[j] != NULL && node != now) {
                node = node -> son[j];
            }

            next -> fail = node;
            q.pb(next);
        }
    }
}

inline void read() {
    char w[LW];
    scanf("%s", a);
    scanf("%d", &n);

    T = new Node;

    for (int i = 0; i < n; ++i) {
        scanf("%s", w);
        ins(T, w, i);
    }

    bfs();
}

inline void reversedBfs() {
    Node* now;

    for (int i = int(q.size()) - 1; i > 0; --i) {
        now = q[i];
        now -> fail -> nr += now -> nr;

        for (vector< int >::iterator it = now -> words.begin(), lim = now -> words.end(); it != lim; ++it) {
            rez[*it] += now -> nr;
        }
    }
}

inline void solve() {
    int next;
    Node *node = T;

    for (int i = 0; a[i] != '\0'; ++i) {
        next = int(a[i] - 'a');

        for (; node != T && node -> son[next] == NULL; node = node -> fail) {
            ;
        }

        if (node -> son[next] != NULL) {
            node = node -> son[next];
            ++(node -> nr);
        }
    }

    reversedBfs();
}

inline void print() {
    for (int i = 0; i < n; ++i) {
        printf("%d\n", rez[i]);
    }
}

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    read();
    solve();
    print();

    return 0;
}