Cod sursa(job #1509018)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2015 13:47:27
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <cstdio>

using namespace std;

int Vec[1000005], Next[1000005], nodesx;

struct Node {
    int cnt, leg[27], bad, adj, parent, c;
} T[1000005];
int root = 1, nodes = 1;

int Where[105];
char Tx[1000005], P[10005];

void addEdge(int a, int b) {
    ++nodesx;
    Vec[nodesx] = b;
    Next[nodesx] = T[a].adj;
    T[a].adj = nodesx;
}

int addWord() {
    int node = root;
    for(int i=0; P[i]; i++) {
        int c = P[i] - 'a';

        if(T[node].leg[c] == 0) {
            T[node].leg[c] = ++nodes;
            T[nodes].parent = node;
            T[nodes].c = c;
        }
        node = T[node].leg[c];
    }

    return node;
}

int Q[1000005], b, e;
void build_bad() {

    Q[e++] = root;
    while(b < e) {
        int node = Q[b++];

        if(node != root) {
            int bad = T[T[node].parent].bad;
            int c = T[node].c;

            while(bad && T[bad].leg[c] == 0) bad = T[bad].bad;
            T[node].bad = (bad) ? T[bad].leg[c] : root;
            addEdge(T[node].bad, node);
        }

        for(int c=0; c<='z'-'a'; c++)
            if(T[node].leg[c])
                Q[e++] = T[node].leg[c];
    }
}

void solve() {
    int node = root;

    for(int i=0; Tx[i]; i++) {
        int c = Tx[i] - 'a';

        while(node && T[node].leg[c] == 0) node = T[node].bad;
        node = (node) ? T[node].leg[c] : root;

        T[node].cnt++;
    }
}

void dfs() {
    e = 0;
    Q[++e] = root;

    while(e) {
        int node = Q[e];

        if(node < 0) {
            e--, node = -node;
            for(int i = T[node].adj; i; i = Next[i])
                T[node].cnt += T[Vec[i]].cnt;
        } else {
            Q[e] = -Q[e];
            for(int i = T[node].adj; i; i = Next[i])
                Q[++e] = Vec[i];
        }
    }
}


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

    int n;

    scanf("%s\n%d", &Tx, &n);
    for(int i=1; i<=n; i++) {
        scanf("%s", &P);
        Where[i] = addWord();
    }

    build_bad();
    solve();
    dfs();

    for(int i=1; i<=n; i++)
        printf("%d\n", T[Where[i]].cnt);
}