Cod sursa(job #3264809)

Utilizator not_anduAndu Scheusan not_andu Data 24 decembrie 2024 11:54:16
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "ahocorasick.in"
#define OUTFILE "ahocorasick.out"

const int LET_MAX = 26;

struct Node {

    int out = 0;
    vector<int> wordIndex;
    Node *fail = nullptr;
    Node *next[LET_MAX] = {};

};

stack<Node*> st;

void add(Node *root, string s, int index){
    Node *current = root;
    for(int i = 0; i < s.length(); ++i){
        if(current -> next[s[i] - 'a'] == nullptr) current -> next[s[i] - 'a'] = new Node;
        current = current -> next[s[i] - 'a'];
    }
    current -> wordIndex.push_back(index);
}

void ahoCorasick(Node *root){
    queue<Node*> q;
    q.push(root);
    st.push(root);
    while(!q.empty()){
        Node *current = q.front(); q.pop();
        for(int i = 'a'; i <= 'z'; ++i){
            if(current -> next[i - 'a'] != nullptr){
                q.push(current -> next[i - 'a']);
                st.push(current -> next[i - 'a']);
                Node *f = current -> fail;
                while(f -> next[i - 'a'] == nullptr && f != root){
                    f = f -> fail;
                }
                if(f -> next[i - 'a'] != nullptr && f -> next[i - 'a'] != current -> next[i - 'a']){
                    f = f -> next[i - 'a'];
                }
                current -> next[i - 'a'] -> fail = f;
            }
        }
    }
}

void revDfs(Node *root, vector<int> &ans){
    while(!st.empty()){
        Node *current = st.top(); st.pop();
        if(current -> fail != nullptr) {
            current -> fail -> out += current -> out;
        }
        for(int i = 0; i < current -> wordIndex.size(); ++i){
            ans[current -> wordIndex[i]] = current -> out;
        }
    }
}

void solve(){
    
    Node *root = new Node;
    root -> fail = root;

    string s; cin >> s;
    int queries; cin >> queries;
    vector<int> ans(queries, 0);

    for(int i = 0; i < queries; ++i){
        string aux; cin >> aux;
        add(root, aux, i);
    }

    ahoCorasick(root);
    Node *current = root;
    for(int i = 0; i < s.length(); ++i){
        while(current -> next[s[i] - 'a'] == nullptr && current != root) current = current -> fail;
        if(current -> next[s[i] - 'a'] != nullptr) current = current -> next[s[i] - 'a'];
        current -> out++;
    }

    revDfs(root, ans);

    for(int i = 0; i < queries; ++i){
        cout << ans[i] << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}