Cod sursa(job #1468234)

Utilizator CollermanAndrei Amariei Collerman Data 5 august 2015 16:02:10
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

const int NMAX = 1000005;
const int MMAX = 10005;

int N;
char A[NMAX], cuv[MMAX];

class Trie
{
    public:
        Trie * fii[26];
        Trie * fail;
        int val;
        vector<Trie*> V;

        Trie() : fail(0), val(0) { memset(fii, 0, sizeof(fii)); }
};

Trie * Root = new Trie();
Trie * cuvinte[105];
queue<Trie*> Q;

void add(Trie * nod, char cuv[], int index)
{
    if(*cuv == 0) {
        cuvinte[index] = nod;
        return;
    }

    if(nod -> fii[*cuv - 'a'] == 0)
        nod -> fii[*cuv - 'a'] = new Trie();

    add(nod -> fii[*cuv - 'a'], cuv + 1, index);
}

void dfs(Trie * nod)
{
    for(auto x : nod -> V) {
        dfs(x);
        nod -> val += x -> val;
    }
}

int main()
{
    fin >> A >> N;
    for(int i=1; i<=N; i++) {
        fin >> cuv;
        add(Root, cuv, i);
    }

    Q.push(Root);
    while(!Q.empty())
    {
        Trie * C = Q.front(); // C = current trie
        Q.pop();

        for(int i=0; i<26; i++) {
            if(C -> fii[i]) {
                Trie * nod = C -> fail;
                while(nod && nod -> fii[i] == 0)
                    nod = nod -> fail;

                if(!nod) {
                    C -> fii[i] -> fail = Root;
                    Root -> V.push_back(C -> fii[i]);
                }
                else {
                    C -> fii[i] -> fail = nod -> fii[i];
                    nod -> fii[i] -> V.push_back(C -> fii[i]);
                }

                Q.push(C -> fii[i]);
            }
        }
    }

    Trie * C = Root;
    for(int i=0; A[i]; i++) {
        while(C && C -> fii[A[i] - 'a'] == 0)
            C = C -> fail;

        if(!C) C = Root;
        else C = C -> fii[A[i] - 'a'];

        (C -> val)++;
    }

    dfs(Root);

    for(int i=1; i<=N; i++)
        fout << cuvinte[i] -> val << '\n';

    return 0;
}