Cod sursa(job #1170425)

Utilizator tudorv96Tudor Varan tudorv96 Data 13 aprilie 2014 16:08:33
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;

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

const int SMAX = 1e6 + 5, WMAX = 1e4 + 5, NMAX = 105;

struct Trie {
    Trie *fiu[26], *fail;
    int frecv;
    vector <int> poz;
    Trie() {
        for (int i = 0; i < 26; ++i)
            fiu[i] = NULL;
        fail = NULL;
        frecv = 0;
    }
} *Root, *Q[WMAX * WMAX];

int st = 1, dr = 1, n, sol[NMAX];
string Input, NOW;

void insertToTrie(string s, int k) {
    Trie *Node = Root;
    int sz = s.size();
    for (int i = 0; i < sz; ++i) {
        int Next = s[i] - 'a';
        if (Node -> fiu[Next] == NULL)
            Node -> fiu[Next] = new Trie;
        Node = Node ->fiu[Next];
    }
    Node -> poz.push_back (k);
}

void bfs() {
    Root->fail = Root;
    Trie *Node, *Crt;
    Q[1] = Root;
    while (st <= dr) {
        Node = Q[st++];
        for (int i = 0; i < 26; ++i)
            if (Node -> fiu[i] != NULL) {
                for (Crt = Node ->fail; Crt != Root && Crt->fiu[i] == NULL; Crt = Crt -> fail);
                if (Crt -> fiu[i] != NULL && Crt -> fiu[i] != Node -> fiu[i])
                    Crt = Crt -> fiu[i];
                Node->fiu[i]->fail = Crt;
                Q[++dr] = Node ->fiu[i];
            }
    }
    Root->fail = NULL;
}

void ahoCorasick() {
    Trie *Node = Root;
    for (int i = 0; i < Input.size(); ++i) {
        int Next = Input[i] - 'a';
        for (; Node->fiu[Next] == NULL && Node != Root; Node = Node -> fail);
        if (Node -> fiu[Next] != NULL)
            Node = Node -> fiu[Next];
       Node -> frecv++;
    }
}

void antiBfs() {
    for (int i = dr; i; --i) {
        Trie *Node = Q[i];
        if (Node -> fail != NULL)
            Node -> fail -> frecv += Node -> frecv;
        for (vector <int> :: iterator it = Node->poz.begin(); it != Node->poz.end(); ++it)
            sol[*it] = Node -> frecv;
    }
}

int main() {
    Root = new Trie;
    fin >> Input >> n;
    for (int i = 0; i < n; ++i) {
        fin >> NOW;
        insertToTrie (NOW, i);// OK
    }
    bfs(); //OK ?
    ahoCorasick(); // OK ?
    antiBfs();//OK ?
    for (int i = 0; i < n; ++i)
        fout << sol[i] << "\n";
}