Cod sursa(job #3250408)

Utilizator MikeStrikeAgache Mihai MikeStrike Data 20 octombrie 2024 18:02:17
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

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

stack<Node*> Stack;

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

void Aho_Corasick(Node *root)
{
    queue<Node*> queue;
    queue.push(root);
    Stack.push(root);
    while(!queue.empty()){
        Node *current = queue.front();
        queue.pop();
        for(int i = 'a'; i <= 'z'; i++){
            if(current->next[i-'a'] != nullptr){
                queue.push(current->next[i-'a']);
                Stack.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 InverseBFS(Node *root, vector<int> &solution)
{
    while(!Stack.empty()){
        Node *current = Stack.top();
        Stack.pop();
        if(current->fail != nullptr){
            current->fail->out += current->out;
        }
        for(int i = 0; i < current->wordIndex.size(); i++){
            solution[current->wordIndex[i]] = current->out;
        }
    }
}


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


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

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

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