Cod sursa(job #3257236)

Utilizator Dani111Gheorghe Daniel Dani111 Data 17 noiembrie 2024 00:24:08
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 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;
    }

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

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

            act->fail = fail(act);
            for(int i = 0; i < 26; i++) {
                if(act->nxt[i] != NULL) q.push(act->nxt[i]);
            }
            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]);
    }

    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){
        i->fail->dp += i->dp;
    }

    
    for(int i = 1; i <= N; i++) {
        cout << fnl[i]->dp << '\n';
    }
}