Cod sursa(job #2431991)

Utilizator Alex18maiAlex Enache Alex18mai Data 21 iunie 2019 15:25:38
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

//#include <iostream>
#include <fstream>
ifstream cin ("ahocorasick.in");ofstream cout ("ahocorasick.out");

string S;
int n;
string s[110];

void citire (){
    cin>>S;
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>s[i];
    }
}

const int lit = 'z'-'a'+1;

struct nod{
    int nxt[lit] , fail , val;
    //string s;
} v[1000100];
int pnt = 0;
int fin[110];

void trie (int nod , int sir , int lv){
    if (lv == s[sir].size()){ fin[sir]=nod; return; }
    if (!v[nod].nxt[s[sir][lv]-'a']){ v[nod].nxt[s[sir][lv]-'a'] = ++pnt; }
    trie (v[nod].nxt[s[sir][lv]-'a'] , sir , lv+1);
}

queue < int > q;
vector < int > ord;

void fail (){
    for (int i=0; i<lit; i++){
        if (v[0].nxt[i]){
            q.push(v[0].nxt[i]);
            //v[v[0].nxt[i]].s = char(i+'a');
        }
    }
    while (!q.empty()){
        int now = q.front();
        //cout<<v[now].s<<" "<<v[v[now].fail].s<<'\n';
        ord.push_back(now);
        q.pop();
        for (int i=0; i<lit; i++){
            if (v[now].nxt[i]){
                int cop = v[now].nxt[i];
                q.push(cop);
                //v[cop].s = v[now].s + char(i+'a');
                v[cop].fail = v[now].fail;
                while (v[cop].fail && !v[v[cop].fail].nxt[i]){
                    v[cop].fail = v[v[cop].fail].fail;
                }
                if (v[v[cop].fail].nxt[i]){
                    v[cop].fail = v[v[cop].fail].nxt[i];
                }
            }
        }
    }
}

void val (){
    int now = 0;
    for (int i=0; i<S.size(); i++){
        while (now && !v[now].nxt[S[i]-'a']){ now = v[now].fail; }
        if (v[now].nxt[S[i]-'a']){ now = v[now].nxt[S[i]-'a']; }
        v[now].val++;
        //cout<<v[now].s<<" ";
    }
    //cout<<'\n';
}

void prop (){
    reverse (ord.begin() , ord.end());
    for (auto &x : ord){ v[v[x].fail].val += v[x].val; }
}


int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    citire();
    for (int i=1; i<=n; i++){
        trie (0 , i , 0);
    }
    fail();
    val();
    prop();
    for (int i=1; i<=n; i++){
        cout<<v[fin[i]].val<<'\n';
    }


    return 0;
}