Cod sursa(job #2921906)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 2 septembrie 2022 13:06:57
Problema Aho-Corasick Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.19 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>
 
using namespace std;


ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
 
struct Node {
    int count;
    string path;
    Node* edges[26];
    Node* fail;
 
    Node() {
        count = 0;
        memset(edges, 0, sizeof(edges));
        fail = nullptr;
    }
} root;
 
void add(Node& root, const string& s) {
    Node* n = &root;
    for (int p = 0; p < s.size(); p++) {
        int c = s[p] - 'a';
        if (n->edges[c] == nullptr) {
            n->edges[c] = new Node();
            n->edges[c]->path = n->path + s[p];
        }
        n = n->edges[c];
    }
}

void dfs(Node& n) {
    g << "[node]: (" <<  n.path << ") [edge]: ";
    for (int i = 0; i < 26; i++) {
        if (n.edges[i] != nullptr) {
            g << "(" << n.edges[i]->path << ") ";
        }
    }
    g << " [fail]: (" << (n.fail != nullptr ? n.fail->path : "null") << ")\n"; 

    for (int i = 0; i < 26; i++) {
        if (n.edges[i] != nullptr) {
            dfs(*(n.edges[i]));
            //n.count += n.edges[i]->count;
        }
    }
}
 
int main() {

    string s;
    int N;

    f >> s;
    f >> N;
    string words[N];
    for (int i = 0; i < N; i++) {
        f >> words[i];
        add(root, words[i]);
    }

    queue<Node*> Q;
    Q.push(&root);

    while (!Q.empty()) {
        Node* n = Q.front();
        Q.pop();

        assert(n == &root || n->fail != nullptr);
        //g << "[q]: (" << n->path << ")\n";

        for (int i = 0; i < 26; i++) {
            if (n->edges[i] == nullptr)
                continue;
            
            Node* fail = n->fail;
            Node* c = n->edges[i];
            Q.push(c);

            if (n == &root) {
                c->fail = n;
                continue;
            }
            assert(fail != nullptr);

            while (fail != &root && fail->edges[i] == nullptr) {
                //g << "[fail]:(" << fail->path << ") ";
                fail = fail->fail;
                assert(fail != nullptr);
            }
            
            if (fail->edges[i] != nullptr)
                c->fail = fail->edges[i];
            else
                c->fail = &root;
            //g << "[c.path]:(" << c->path << ") [fail]:(" << c->fail->path << ")\n";
        }
    }

    Node* n = &root;
    //cout << n << '\n';
    for (int i = 0; i < s.size(); i++) {
        int c = s[i] - 'a';
        while (n != &root && n->edges[c] == nullptr)
            n = n->fail;
        
        if (n->edges[c] != nullptr)
            n = n->edges[c];
        assert(n != nullptr);
        for (Node* x = n; x != &root; x = x->fail)
            ++x->count;
        //g << i%10 << " (" << s[i] << ") [at]: (" << n->path << ")\n";
        //++n->count;
        //cout << n << ' ' << n->count << '\n';
    }

    //dfs(root);

    for (int i = 0; i < N; i++) {
        n = &root;
        for (int j = 0; j < words[i].size(); j++) {
            n = n->edges[words[i][j] - 'a'];
            assert(n != nullptr);
        }
        g << n->count << '\n';
    }


 
    f.close();
    g.close();
    return 0;
}