Cod sursa(job #2645553)

Utilizator AlexNeaguAlexandru AlexNeagu Data 28 august 2020 21:11:50
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>
using namespace std;
const int D = 27;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");


vector<int> us, Q;

struct Vertex {

    int f, link;
    vector<int> nxt;
    Vertex() {
        f = 0, link;
        nxt.assign(D, -1);
    }
};

struct AC {

    vector<Vertex> trie;
    AC() {
        trie.resize(1);
    }

    void insert(string &s) {

        int node = 0;
        for(char c : s) {
            int x = c - 'a';
            if(trie[node].nxt[x] == -1) {
                trie[node].nxt[x] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].nxt[x];
        }
        us.push_back(node);
    }

    void build() {

        Q.push_back(0);
        trie[0].link = 0;

        for(int i = 0; i < Q.size(); i++) {

            int node = Q[i];

            for(int x = 0; x < D; x++) {

                if (trie[node].nxt[x] == -1) continue;

                int now = trie[node].link;
                while(now && trie[now].nxt[x] == -1) now = trie[now].link;
                if(trie[now].nxt[x] != -1 && trie[now].nxt[x] != trie[node].nxt[x]) {
                    now = trie[now].nxt[x];
                }

                Q.push_back(trie[node].nxt[x]);
                trie[trie[node].nxt[x]].link = now;
            }
        }
    }
    
    void get_ans(string &me) {

        int node = 0;
        for(char c : me) {

            int x = c - 'a';
            while(trie[node].nxt[x] == -1 && node) {
                node = trie[node].link;
            }

            if(trie[node].nxt[x] != -1) {
                node = trie[node].nxt[x];
            }

            //cout << node << '\n';
            trie[node].f += 1;

        }

        for(int i = Q.size() - 1; i >= 0; i--) {
            trie[trie[Q[i]].link].f += trie[Q[i]].f;
        }

        for(auto it : us) {
            out << trie[it].f << '\n';
        }
    }

};  

 
int main() {
    
    ios_base::sync_with_stdio(0); cin.tie(0);    
    
    string t;
    in >> t;

    int n;
    in >> n;

    AC aho;

    for(int i = 0; i < n; i++) {
        string s;
        in >> s;
        aho.insert(s);
    }

    aho.build();
    aho.get_ans(t);
    
    return 0;
}