Cod sursa(job #1688188)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 aprilie 2016 12:18:50
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>

using namespace std;

const int sigma = 26;

const int nmax = 100 + 10;
const int lmax = 10000 + 10;
const int vmax = nmax * lmax;

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

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

trie *root , *info[nmax];

int n , i;
string sir , s;

int dim;
pair < trie * , int > q[vmax];

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

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

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

void bagaphi()
{
    root -> phi = root; root -> prv = root; //!!!!

    for (int i = 0; i < sigma; ++i)
        if (root -> son[i] != NULL)
        {
            root -> son[i] -> phi = root;
            q[++dim] = {root -> son[i] , i};
        }

    for (int j = 1; j <= dim; ++j)
    {
        trie *node; int act;
        tie(node , act) = q[j];

        for (int i = 0; i < sigma; ++i)
            if (node -> son[i] != NULL)
                q[++dim] = {node -> son[i] , i};

        if (node -> prv == root) continue;

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

        node -> phi = k;
    }
}

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

        k -> cnt++;
    }

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

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

    root = new trie;

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

    bagaphi();
    bagakmp(); ///aho aho

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

    return 0;
}