Mai intai trebuie sa te autentifici.

Cod sursa(job #1736812)

Utilizator retrogradLucian Bicsi retrograd Data 2 august 2016 17:11:28
Problema Aho-Corasick Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 2.95 kb
#include <bits/stdc++.h>

using namespace std;

struct SuffixAutomaton {
    struct Node {
        int link, len;
        map<char, int> leg;
    };
    vector<Node> T;
    int last = 0, nodes = 1;

    SuffixAutomaton(int sz) {
        T.resize(sz);
        T[0].link = -1;
        T[0].len = 0;
        occurences.resize(sz);
    }

    // Adds another character to the automaton
    void ConsumeChar(char c) {
        // Add state for whole string
        int cur = nodes++;
        T[cur].len = T[last].len + 1;
        T[cur].link = 0;

        int node = last;

        // Add transitions to all suffixes which do not have one already
        while(node != -1 && T[node].leg.count(c) == 0) {
            T[node].leg[c] = cur;
            node = T[node].link;
        }

        if(node != -1) {
            // We found double-edge
            int old = T[node].leg[c];

            if(T[old].len == T[node].len + 1) {
                // Just set a new link
                T[cur].link = old;
            } else {
                // We have to split one edge
                int clone = nodes++;

                T[clone].leg = T[old].leg;
                T[clone].len = T[node].len + 1;
                T[clone].link = T[old].link;
                
                // Set the "good" links
                T[old].link = T[cur].link = clone;
                
                // Rewire classes pointing to old
                while(node != -1 && T[node].leg[c] == old) {
                    T[node].leg[c] = clone;
                    node = T[node].link;
                }
            }
        }

        last = cur;
        occurences[cur] += 1;
    }

    vector<int> occurences;
    void CountOccurences() {
        queue<int> Q;
        vector<int> degree(nodes);

        for(int i = 1; i < nodes; ++i)
            degree[T[i].link] += 1;

        for(int i = 0; i < nodes; ++i) 
            if(degree[i] == 0) {
                Q.push(i);
            }

        while(!Q.empty()) {
            int i = Q.front();
            Q.pop();
            if(i == 0) continue;

            occurences[T[i].link] += occurences[i];
            if(--degree[T[i].link] == 0)
                Q.push(T[i].link);
        }
    }
};
SuffixAutomaton automaton(200005);

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    string text, word;
    cin >> text;

    for(auto c : text)
        automaton.ConsumeChar(c);
    automaton.CountOccurences();

    int n;
    cin >> n;

    while(n--) {
        cin >> word;
        int node = 0;

        for(char c : word) {
            if(automaton.T[node].leg.count(c) == 0) {
                node = -1;
                break;
            }
            node = automaton.T[node].leg[c];
        }

        if(node == -1) cout << "0\n";
        else cout << automaton.occurences[node] << '\n';
    }

    return 0;
}