Cod sursa(job #2187483)

Utilizator antanaAntonia Boca antana Data 26 martie 2018 16:02:19
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fi( "ahocorasick.in" ); ofstream fo( "ahocorasick.out" );

const int maxn  = 1e6 + 5;
const int maxl  = 1e4 + 5;
const int maxw  = 105;
const int sigma = 26;

struct trie {
    int match;
    trie *son[sigma], *fail;
    vector <int> pos;
    trie() {
        memset(son, 0, sizeof son);
        fail = 0;
        match = 0;
        pos.clear();
    }
} *root;

char s[maxn], word[maxl];
int n, length, ans[maxw], l, r;

void tinsert(trie *node, char *str, int idx) {
    if (*str == 0) {
        node->pos.push_back(idx);
        return;
    }
    if (node->son[*str - 'a'] == NULL)
        node->son[*str - 'a'] = new trie();
    tinsert(node->son[*str - 'a'], str + 1, idx);
}


trie* q[maxn];

void bfs() {
    trie *node, *aux;

    l = r = 0;
    root->fail = root;
    q[r++] = root;
    while (l < r) {
        node = q[l++];
        for (int i = 0; i < sigma; i++) {
            if (node->son[ i ] == NULL)
                continue;
            aux = node->fail;
            while (aux != root && aux->son[ i ] == NULL)
                aux = aux->fail;
            if (aux->son[ i ] != NULL && aux->son[ i ] != node->son[ i ])
                aux = aux->son[ i ];
            node->son[ i ]->fail = aux;
            q[r++] = node->son[ i ];
        }
    }
    root->fail = NULL;
}

void solve() {
    length = strlen(s);
    trie *aux = root;
    for (int i = 0; i < length; i++) {
        while (aux != NULL && aux->son[s[ i ] - 'a'] == NULL && aux != root)
            aux = aux->fail;
        if (aux->son[s[ i ] - 'a'] != NULL)
            aux = aux->son[s[ i ] - 'a'];
        aux->match++;
    }
}

void antibfs() {
    trie *node;
    for (int i = r - 1; i >= 0; i--) {
        node = q[ i ];
        if (node->fail != NULL)
            node->fail->match += node->match;
        for (int idx: node->pos)
            ans[ idx ] = node->match;
    }
}

int main()
{
    fi >> s >> n;
    root = new trie();
    for (int i = 1; i <= n; i++) {
        fi >> word;
        tinsert(root, word, i);
    }

    bfs();
    solve();
    antibfs();

    for (int i = 1; i <= n; i++)
        fo << ans[ i ] << "\n";

    fo.close();
    fi.close();

    return 0;
}