Cod sursa(job #2723971)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 15 martie 2021 23:27:34
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

struct node {
    node* to[26]; node* lps; int nr;
    node() {memset(to, NULL, sizeof(to)); lps = NULL; nr = 0;}
    node* go_to(char ch) { if(!to[ch - 'a']) return to[ch - 'a'] = new node(); return to[ch - 'a']; }
};

class Trie {
private:
    vector <node*> t, nodes;
    int k, n;
public:
    node* root = new node();
    void build(vector <string>& v) {
        root -> lps = root; n = (int)v.size();
        /// Building the dictionary
        for(auto s : v) {
            node* curr = root;
            for(auto ch : s) curr = curr -> go_to(ch);
            t.push_back(curr);
        }
        node* aux; nodes.push_back(root); k = 0;
        /// BFS & getting lps for every node
        while(k < (int)nodes.size()) {
            node* top = nodes[k++];
            for(short ch = 0; ch < 26; ch++) if(top -> to[ch]) {
                for(aux = top -> lps; aux != root && !aux -> to[ch]; aux = aux -> lps);
                if(aux -> to[ch] && aux != top) top -> to[ch] -> lps = aux -> to[ch];
                else top -> to[ch] -> lps = root;
                nodes.push_back(top -> to[ch]);
            }
        }
    }
    Trie() {}
    Trie(vector <string>& v) {build(v);}

    vector <int> get_occurences(string s) {
        int len = s.length(); node* sn = root;
        /// Traverse trie & add 1 at every node, return to lps while there's no route
        for(int i = 0; i < len; i++) {
            short ch = s[i] - 'a';
            for(; sn != root && !sn -> to[ch]; sn = sn -> lps);
            if(sn -> to[ch]) sn = sn -> to[ch];
            sn -> nr++;
        }
        /// Add nr to nodes -> lps -> nr, the patterns recognized at lps(u), and only those,
        /// are proper suffixes of L(u), and shall thus be recognized at state u as well
        for(int i = k - 1; i >= 0; i--) nodes[i] -> lps -> nr += nodes[i] -> nr;
        vector <int> res(n);
        /// Set res for every word
        for(int i = 0; i < n; i++) res[i] = t[i] -> nr;
        return res;
    }
};

string s;
vector <string> dict;
int n;

int main()
{
    fin >> s;
    fin >> n; dict.resize(n);
    for(int i = 0; i < n; i++)
        fin >> dict[i];

    Trie T(dict);
    vector <int> sol = T.get_occurences(s);
    for(int i = 0; i < n; i++)
        fout << sol[i] << "\n";
    return 0;
}