Cod sursa(job #2765223)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 25 iulie 2021 19:52:38
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("ahocorasick.in");
ofstream out("ahocorasick.out");

class ahoCorasick{
public:
    struct aCNode{
        aCNode * nxt[26], * backRef;
        int nrMch;
        aCNode(){
            fill(nxt, nxt+26, nullptr);
            backRef = nullptr;
            nrMch = 0;
        }
    };
    ahoCorasick(){
        root = new aCNode();
    }
    aCNode * addString(const string & s){
        aCNode * nod = root;
        for(auto &x: s){
            if(nod->nxt[x-'a']==nullptr)
                nod->nxt[x-'a']=new aCNode();
            nod=nod->nxt[x-'a'];
        }
        return nod;
    }
    void buildAutomata(){
        root->backRef = root;
        vecS.push_back(root);
        for(char i=0; i<26; i++)
            if(root->nxt[i]!=nullptr)
                vecS.push_back(root->nxt[i]), root->nxt[i]->backRef=root;
            else
                root->nxt[i] = root;

        for(int st=1; st<vecS.size(); st++){
            aCNode * nNow=vecS[st];
            for(char i=0; i<26; i++)
                if(nNow->nxt[i]!=nullptr)
                    vecS.push_back(nNow->nxt[i]), nNow->nxt[i]->backRef=nNow->backRef->nxt[i];
                else
                    nNow->nxt[i] = nNow->backRef->nxt[i];
        }
    }
    void eatString(string & s){
        aCNode * node = root;
        for(auto &x:s)
            node = node->nxt[x-'a'], node->nrMch++;
        for(int i=vecS.size()-1; i>0; i--)
            vecS[i]->backRef->nrMch+=vecS[i]->nrMch;
    }
private:
    aCNode * root;
    vector <aCNode *> vecS;
};
ahoCorasick::aCNode * a[102];
int main()
{
    string s;
    in>>s;
    int n;
    in>>n;
    ahoCorasick arb;
    for(int i=1; i<=n; i++){
        string p;
        in>>p;
        a[i] = arb.addString(p);
    }
    arb.buildAutomata();
    arb.eatString(s);

    for(int i=1; i<=n; i++)
        out<<a[i]->nrMch<<"\n";
    return 0;
}