Cod sursa(job #1232745)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 23 septembrie 2014 20:33:28
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.88 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>

using namespace std;

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

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

const int SIGMA = 30;
const int MAXA = 1000005;
const int MAXW = 10005;
const int MAXN = 105;
const int oo = 0x3f3f3f3f;

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; }

struct Trie {
    int matches;
    Trie *sons[SIGMA], *fail;
    vector <int> where;
    Trie () {
        memset(sons, NULL, sizeof(sons));
        matches = 0;
    }
};

char A[MAXA], s[MAXW];
int N, p, u, Ans[MAXN];
Trie *Root = new Trie(), *Q[MAXN * MAXW];

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

inline void BFs() {
    Trie *K;
    Root->fail = Root;
    for(Q[p = u = 1] = Root ; p <= u ; ++ p) {
        Trie *Node = Q[p];
        for(int son = 0 ; son < SIGMA ; ++ son)
            if(Node->sons[son]) {
                for(K = Node->fail; K != Root && K -> sons[son] == NULL ; )
                    K = K->fail;
                if(K->sons[son] && K->sons[son] != Node->sons[son]) /// to prevent K for pointing to the same node
                    K = K->sons[son];
                Node->sons[son]->fail = K;
                Q[++u] = Node->sons[son];
            }
    }
}

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

int main() {
    fin >> (A + 1);
    fin >> N;
    for(int i = 0 ; i < N ; ++ i) {
        fin >> s;
        Insert(Root, s, i);
    }
    BFs();
    Trie *K = Root;
    int M = strlen(A + 1);
    for(int i = 1 ; i <= M ; ++ i) {
        int son = A[i] - 'a';
        while(K != Root && K -> sons[son] == NULL)
            K = K->fail;
        if(K->sons[son])
            K = K->sons[son];
        ++ K->matches;
    }
    revBFs();
    for(int i = 0 ; i < N ; ++ i)
        fout << Ans[i] << '\n';
    fin.close();
    fout.close();
    return 0;
}