Cod sursa(job #1813845)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 23 noiembrie 2016 13:46:46
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

const int sigma = 26;

const int nmax = 1e2 + 10;
const int lmax = 1e4 + 10;
const int dmax = nmax * lmax;

struct trie {
    trie *phi, *son[sigma];
    int cnt;

    trie() {
        phi = NULL;
        for (int i = 0; i < sigma; ++i) son[i] = NULL;
        cnt = 0;
    }
};

string str, s;

int dim, n;
trie *q[dmax];

trie *root, *whr[nmax];

trie *add(trie *node, int pos) {
    if (pos == (int)s.size())
        return node;

    int to = s[pos] - 'a';
    if (node -> son[to] == NULL)
        node -> son[to] = new trie;

    return add(node -> son[to], pos + 1);
}

void compute_phi() {
    root -> phi = root;

    q[++dim] = root;
    for (int it = 1; it <= dim; ++it) {
        trie *node = q[it];
        for (int i = 0; i < sigma; ++i) {
            if (node -> son[i] == NULL) continue;

            trie *k = node -> phi;
            while (k != root && k -> son[i] == NULL)
                k = k -> phi;

            if (k -> son[i] != NULL && k != node) k = k -> son[i];
            node -> son[i] -> phi = k;

            q[++dim] = node -> son[i];
        }
    }
}

void compute_aho() {
    trie *k = root;
    for (int i = 0; i < (int)str.size(); ++i) {
        int to = str[i] - 'a';
        while (k != root && k -> son[to] == NULL)
            k = k -> phi;

        if (k -> son[to] != NULL) k = k -> son[to];
        k -> cnt++;
    }

    for (int i = dim; i ; --i)
        q[i] -> phi -> cnt += q[i] -> cnt;
}

int main()
{
    ifstream fin("ahocorasick.in");
    ofstream fout("ahocorasick.out");

    root = new trie;
    fin >> str;

    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> s;
        whr[i] = add(root, 0);
    }

    compute_phi();
    compute_aho();

    for (int i = 1; i <= n; ++i)
        fout << whr[i] -> cnt << '\n';

    return 0;
}