Cod sursa(job #825205)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 27 noiembrie 2012 20:48:22
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>

using namespace std;

#define MAXA 1000050
#define MAXB 10050
#define MAXN 105
char A[MAXA], B[MAXB];
int N, k, nr;
int pi, ps;
int ans[MAXN];

struct ac {
    ac *f[26];
    ac *fail;
    int num;
    vector<int> lst;

    ac() {
        num = 0;
        fail = NULL;
        for(int i = 0; i < 26; i++)
            f[i] = NULL;
    }
} *root, *p, *Q[MAXB * MAXB];

void insert(ac *node, char *str, int idx) {
    if(!isalpha(*str)) {
        node->lst.push_back(idx);
        return;
    }

    int next = *str - 'a';
    if(node->f[next] == NULL)
        node->f[next] = new ac();
    insert(node->f[next], str + 1, idx);
}

void bfs() {
    root->fail = root;
    Q[1] = root;
    for(pi = ps = 1; ps <= pi; ps++) {
        ac *fr = Q[ps];

        for(int i = 0; i < 26; i++)
            if(fr->f[i] != NULL) {
                ac *aux = fr->fail;
                for(;aux->f[i] == NULL && aux != root; aux = aux->fail);

                if(aux->f[i] != NULL && aux->f[i] != fr->f[i])
                    aux = aux->f[i];

                fr->f[i]->fail = aux;
                Q[++pi] = fr->f[i];
            }
    }
    root->fail = NULL;
}

void antibfs() {
    for(int i = ps - 1; i > 1; i--) {
        ac *fr = Q[i];

        fr->fail->num += fr->num;

        for(vector<int> :: iterator it = fr->lst.begin(); it != fr->lst.end(); it++)
            ans[*it] = fr->num;
    }
}

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

    fgets(A, sizeof(A), stdin);
    scanf("%d\n", &N);

    root = new ac();

    for(int i = 0; i < N; i++) {
        fgets(B, sizeof(B), stdin);
        insert(root, B, i);
    }

    bfs();

    p = root;
    for(int i = 0; isalpha(A[i]); i++) {
        int next = A[i] - 'a';
        while(p->f[next] == NULL && p != root)
            p = p->fail;

        if(p->f[next] != NULL) {
            p = p->f[next];
            p->num++;
        }
    }

    antibfs();

    for(int i = 0; i < N; i++)
        printf("%d\n", ans[i]);

	return 0;
}