Cod sursa(job #1074308)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 7 ianuarie 2014 15:31:20
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 kb
#include <fstream>
#include <list>
#include <bitset>
#include <string.h>

using namespace std;

const char infile[] = "ahocorasick.in";
const char outfile[] = "ahocorasick.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXL = 1000005;
const int oo = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXS = 10005;
const int SIGMA = 26;
const char DELTA = 'a';

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, p, u, Ans[MAXN];
char A[MAXL], S[MAXS];

struct Trie {
    int matches;
    Trie *sons[SIGMA], *fail;
    list <int> where; /// TODO: implement the arrays as a linked list
    Trie() {   /// constructor
        where.clear(); /// not needed
        memset(sons, 0, sizeof(sons));
        fail = 0;
        matches = 0;
    }
};

Trie *Root = new Trie(), *P, *Q[MAXN * MAXS];

void Insert(Trie * Node, const char *p, const int &ind) {
    if(!*p) {
        Node -> where.push_back(ind);
        return;
    }
    int son = *p - DELTA;
    if(!Node -> sons[son])
        Node -> sons[son] = new Trie();
    Insert(Node -> sons[son], p + 1, ind);
}

inline void BFs(Trie* stNode) {
    Trie *tmp;
    stNode -> fail = stNode;
    for(Q[p = u = 1] = stNode ; p <= u ; ++ p) {
        Trie *Node = Q[p];
        for(int i = 0 ; i < SIGMA ; ++ i)
            if(Node -> sons[i]) {
                for(tmp = Node -> fail ; tmp != stNode && !(tmp -> sons[i]) ; tmp = tmp -> fail);

                if(tmp -> sons[i] && tmp -> sons[i] != Node -> sons[i])
                    tmp = tmp -> sons[i];

                Node -> sons[i] -> fail = tmp;
                Q[ ++ u ] = Node -> sons[i];
            }
    }
    stNode -> fail = 0;
}

inline void revBFs(const Trie* stNode) {
    for(int i = u ; i ; -- i) {
        Trie *Node = Q[i];
        if(Node -> fail)
            Node -> fail -> matches += Node -> matches;
        for(list <int> :: iterator it = Node -> where.begin(), fin = Node -> where.end(); it != fin ; ++ it)
            Ans[*it] = Node -> matches;
    }
}

int main() {
    fin.getline(A, MAXL);
    int L = strlen(A);
    fin >> N;
    fin.get();
    for(int i = 0 ; i < N ; ++ i) {
        fin.getline(S, MAXS);
        Insert(Root, S, i);
    }
    BFs(Root);
    P = Root;
    for(int i = 0 ; i < L ; ++ i) {
        int son = A[i] - DELTA;
        for( ; (!P -> sons[son]) && P != Root ; P = P -> fail);

        if(P -> sons[son])
            P = P -> sons[son];

        ++ P -> matches;
    }
    revBFs(Root);
    for(int i = 0 ; i < N ; ++ i)
        fout << Ans[i] << '\n';
    fin.close();
    fout.close();
    return 0;
}