Cod sursa(job #1688217)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 aprilie 2016 12:32:55
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 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;
    trie *son[sigma];

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

trie *root , *info[nmax] , *q[vmax];

int n , i;
string sir , s;

int dim;

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;

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

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

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

        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 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] -> phi -> cnt += q[i] -> 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;
}