Cod sursa(job #2333512)

Utilizator refugiatBoni Daniel Stefan refugiat Data 1 februarie 2019 12:19:03
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream si("ahocorasick.in");
ofstream so("ahocorasick.out");
int sol[105];
string s,c;

struct trie {
    trie *f[26],*fail;
    int val;
    vector<int> poz;
    trie() {
        memset(f,0,sizeof(f));
        fail = NULL;
        val = 0;
    }
}*t;
inline void add(int x) {
    trie *nod=t;
    for(int i=0; i<c.size(); ++i) {
        if(nod->f[c[i]-'a']==NULL) {
            nod->f[c[i]-'a']=new trie();
        }
        nod=nod->f[c[i]-'a'];
    }
    nod->poz.push_back(x);
}
vector<trie*> v;
inline void bfs() {
    trie *nod;
    v.push_back(t);
    t->fail=t;
    for(int i=0; i<v.size(); ++i) {
        for(int j=0; j<26; ++j) {
            if(v[i]->f[j]!=NULL) {
                nod=v[i]->fail;
                while(nod->f[j]==NULL&&nod!=t) {
                    nod=nod->fail;
                }
                if(nod->f[j]!=NULL&&nod->f[j]!=v[i]->f[j]) {
                    nod=nod->f[j];
                }
                v[i]->f[j]->fail=nod;
                v.push_back(v[i]->f[j]);
            }
        }
    }
}
inline void bfs2() {
    for(int i=v.size()-1; i>=0; --i) {
        if(v[i]->fail!=NULL) {
            v[i]->fail->val+=v[i]->val;
        }
        for(int j=0; j<v[i]->poz.size(); ++j) {
            sol[v[i]->poz[j]]+=v[i]->val;
        }
    }
}
int main() {
    int n;
    si>>s;
    si>>n;
    t=new trie();
    for(int i=1; i<=n; ++i) {
        si>>c;
        add(i);
    }
    bfs();
    trie *nod=t;
    for(int i=0; i<s.size(); ++i) {
        while(nod->f[s[i]-'a']==NULL&&nod!=t) {
            nod=nod->fail;
        }
        if(nod->f[s[i]-'a']!=NULL)
            nod=nod->f[s[i]-'a'];
        nod->val++;
    }
    bfs2();
    for(int i=1; i<=n; ++i)
        so<<sol[i]<<'\n';
    return 0;
}