Cod sursa(job #1705176)

Utilizator retrogradLucian Bicsi retrograd Data 20 mai 2016 00:23:29
Problema Aho-Corasick Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

const int MAXN = 300005; 
 
typedef tree<
char,
int,
less<char>,
ov_tree_tag,
null_node_update>
ordered_set;

struct AhoCorasick {
 
    struct Node {
        int cnt, bad, adj, parent;
        char c;
        ordered_set leg;
    };
    vector<Node> T;
    int root = 1, nodes = 1;

    AhoCorasick(int sz) {
        T.resize(sz);
    }

    int addWord(const string &word) {
        int node = root;
        for(auto c : word) {
            
            auto &nxt = T[node].leg[c];

            if(nxt == 0) {
                nxt = ++nodes;
                T[nodes].parent = node;
                T[nodes].c = c;
            }

            node = nxt;
        }
     
        return node;
    }
     
    queue<int> Q;
    void buildBad() {
     
        Q.push(root);
        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();
     
            
            int bad = T[T[node].parent].bad;
            char c = T[node].c;
 
            while(bad && T[bad].leg.find(c) == T[bad].leg.end()) 
                bad = T[bad].bad;

            T[node].bad = (node == root) ? 0 : (bad) ? T[bad].leg[c] : root;

            for(auto p : T[node].leg)
                Q.push(p.second);
        }
    }

    vector<int> Deg, Sol;

    void parseText(const string &text) {
        int node = root;

        Sol.resize(nodes + 1);
        for(auto c : text) {
            while(node && T[node].leg.find(c) == T[node].leg.end())
                node = T[node].bad;
            node = node ? T[node].leg[c] : root;
            assert(node > 0);
            Sol[node] += 1;
        }
    }

    void dfs() {
        Deg.resize(nodes + 1);
        for(int i = 2; i <= nodes; ++i)
            Deg[T[i].bad] += 1;

        for(int i = 1; i <= nodes; ++i)
            if(Deg[i] == 0)
                Q.push(i);

        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();

            Sol[T[node].bad] += Sol[node];
            if(--Deg[T[node].bad] == 0)
                Q.push(T[node].bad);
        }
    }
};

AhoCorasick A(MAXN);
string text, word;
vector<int> Where;

int main() {
    ifstream cin("ahocorasick.in");
    ofstream cout("ahocorasick.out");

    int n;
    cin >> text;
    
    cin >> n;
    Where.resize(n);

    for(int i = 0; i < n; ++i) {
        cin >> word;
        Where[i] = A.addWord(word);
    }

    A.buildBad(); 
    A.parseText(text); 
    A.dfs(); 

    for(auto q : Where) {
        cout << A.Sol[q] << '\n';
    }

    return 0;
 }