Cod sursa(job #3257235)

Utilizator Dani111Gheorghe Daniel Dani111 Data 17 noiembrie 2024 00:22:29
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.15 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e2;
string A[MAX + 3];
int N;
struct Nod{
        int cnt;
        Nod *fail;
        Nod *nxt[28];
        Nod *par;
        int chr;
        int dp;

        Nod() {
            cnt = 0;
            dp = 0;
            for(int i = 0; i < 26; i++) { 
                nxt[i] = NULL;
            }
            fail = NULL;
        }
};

Nod *fnl[MAX + 3];
vector<Nod*>bfs;
int idx;


struct AhoCorasick{


    

    Nod *root;

    AhoCorasick() {
        root = new Nod;
    }

    void insert(string &s) {
        Nod *curr = root;

        for(int i = 0; i < s.size(); i++) {
            if(curr->nxt[s[i] - 'a'] == NULL) {
                curr->nxt[s[i] - 'a'] = new Nod;
            }
            curr->nxt[s[i] - 'a']->par = curr;
            curr->nxt[s[i] - 'a']->chr = s[i] - 'a';
            curr = curr->nxt[s[i] - 'a'];
        }
        curr->cnt++;
        fnl[idx] = curr;
    }

    Nod *fail(Nod *curr) {
        
        if(curr->fail != NULL) {
            return curr->fail;
        }
        if(curr == root || curr->par == root) return root;

        Nod *ans = curr->par->fail;
        while(ans != root && ans->nxt[curr->chr] == NULL) {
            ans = ans->fail;
        }
        if(ans->nxt[curr->chr] != NULL)
        return ans->nxt[curr->chr];
        return ans;
    }

    // Nod parcurg(Nod * curr, int chr) {
    //     if(curr->nxt[chr] != NULL) return *curr->nxt[chr];
    //     if(curr == root) return *curr;
    //     Nod ans = *parcurg(fail(curr), chr);
    //     return *ans;
    // }

    void build() {
        queue<Nod*>q;
        q.push(root);

        while(!q.empty()) {
            bfs.push_back(q.front());
            Nod *act = q.front();

            act->fail = fail(act);
            //cout << act->chr << ' ' << act->fail->chr << '\n';
            for(int i = 0; i < 26; i++) {
                if(act->nxt[i] != NULL) q.push(act->nxt[i]);
            }
            //act->dp = act->fail->dp + act->cnt;
            q.pop();
        }
    }


}aho;

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        idx = i;
        aho.insert(A[i]);
    }

    //sort(A + 1, A + N + 1);


    aho.build();
    int ans = 0;
    Nod *start = aho.root;
    for(int i = 0; i < s.size(); i++) {
        while(start->nxt[s[i] - 'a'] == NULL && start != aho.root) {
            start = start->fail;
        }
        if(start->nxt[s[i] - 'a'] != NULL) {
            start = start->nxt[s[i] - 'a'];
        }
        start->dp++;
    }

    reverse(bfs.begin(), bfs.end());

    
    // for(auto i : bfs) {
    //     cout << i->dp << ' ' << i->chr << '\n';
    // }
    for(auto i : bfs){
        //cout << (i->dp) << ' ';
        i->fail->dp += i->dp;
    }
    for(int i = 1; i <= N; i++) {
        cout << fnl[i]->dp << '\n';
    }
    //cout << ans;
}