Cod sursa(job #2827355)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 5 ianuarie 2022 17:26:54
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int LGCUV = 10005;
const int NMAX = 1000005;
char a[NMAX],cuv[LGCUV];
int n;
struct Trie{
    int cnt;
    Trie *fiu[26],*back;
    vector<Trie*> v;
    Trie(){
        cnt=0;
        for(int i=0;i<26;i++)
            fiu[i]=NULL;
        back=NULL;
        v.clear();
    }
};
Trie *root = new Trie;
Trie *rasp[105];
Trie *update(Trie *node,char *ch){
    if(*ch==0) return node;
    if(node->fiu[*ch-'a']==NULL)
        node->fiu[*ch-'a']= new Trie;
    return update(node->fiu[*ch-'a'],ch+1);
}
void bfs(){
    queue <Trie*> q;
    q.push(root);
    while(!q.empty()){
        Trie *node = q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(node->fiu[i]==NULL) continue;
            Trie *b = node->back;
            while(b!=NULL and b->fiu[i]==NULL) b=b->back;
            if(b==NULL) b=root;
            else        b=b->fiu[i];
            node->fiu[i]->back = b;
            b->v.push_back(node->fiu[i]);
            q.push(node->fiu[i]);
        }
    }
}
void dfs(Trie *node){
    vector<Trie*>::iterator i;
    for(i=node->v.begin();i!=node->v.end();i++){
        dfs(*i);
        node->cnt+=(*i)->cnt;
    }
}
int main()
{
    fin >> a;
    fin >> n;
    for(int i=1;i<=n;i++){
        fin >> cuv;
        rasp[i]=update(root,cuv);
    }
    bfs();
    Trie *nod = root;
    for(char *ch=a;*ch;ch++){
        while(nod!=NULL and nod->fiu[*ch-'a']==NULL)
            nod=nod->back;
        if(nod==NULL) nod=root;
        else          nod=nod->fiu[*ch-'a'];
        nod->cnt++;
    }
    dfs(root);
    for(int i=1;i<=n;i++){
        fout << rasp[i]->cnt << '\n';
    }
    return 0;
}