Cod sursa(job #3245233)

Utilizator BucsMateMate Bucs BucsMate Data 27 septembrie 2024 23:12:17
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <stack>

using namespace std;

ifstream input("ahocorasick.in");
ofstream output("ahocorasick.out");

struct Node
{
    int out = 0;
    vector<int> ends;
    Node *fail = nullptr;
    Node *next['z' - 'a' + 1] = {};
};

stack<Node*> st;

void add(Node *root, string str, int index)
{
    Node *akt = root;
    for(int i = 0; str[i] != '\0'; i++){
        if(akt->next[str[i]-'a'] == nullptr){
            akt->next[str[i]-'a'] = new Node;
        }
        akt = akt->next[str[i]-'a'];
    }
    akt->ends.push_back(index);
}

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

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


int main()
{
    Node *root = new Node;
    int n;
    string A;
    input >> A >> n;
    vector<int> solution(n, 0);

    for(int i = 0; i < n; i++){
        string temp;
        input >> temp;
        add(root, temp, i);
    }

    construct_AC(root);

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

    InverseBFS(root, solution);

    for(int i = 0; i < n; i++){
        output << solution[i] << endl;
    }
    return 0;
}