Cod sursa(job #2285906)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 19 noiembrie 2018 15:00:01
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.34 kb
#include <bits/stdc++.h>
  
using namespace std;
  
#if 1
    #define pv(x) cerr<<#x<<" = "<<(x)<<"; ";cerr.flush()
    #define pn cerr<<endl
#else
    #define pv(x)
    #define pn
#endif
  
// #if 1
#ifdef INFOARENA
    ifstream in("ahocorasick.in");
    ofstream out("ahocorasick.out");
#else
    #define in cin
    #define out cout
#endif
  
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld, ld>;
using pdd = pair<double, double>;
#define pb push_back
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862;
const long double EPS = 1e-8;
const int inf_int = 1e9 + 5;
const ll inf_ll = 1e18 + 5;
const int NMax = 2e5 + 5;
const int mod = 666013;
const int dx[] = {-1,0,0,+1}, dy[] = {0,-1,+1,0};

struct trieNode {
    trieNode* nxt[26] = {};
    trieNode* blue = this, *green = this;
    vector<int> wordIndex;
    trieNode() {
        for (int c = 0; c < 26; ++c) {
            nxt[c] = nullptr;
        }
    }
} root;

void add(trieNode* node, const string& word, uint idx, int widx) {
    if (idx == word.size()) {
        node->wordIndex.pb(widx);
        return;
    }

    int let = word[idx] - 'a';
    if (node->nxt[let] == nullptr) {
        node->nxt[let] = new trieNode;
    }
    add(node->nxt[let], word, idx + 1, widx);
}

void build(trieNode* node, trieNode* root) {
    if (node->blue->wordIndex.size() != 0) {
        node->green = node->blue;
    }
    else {
        node->green = node->blue->green;
    }

    // pv(word);pn; /////
    // pv(node);pv(node->myCnt);pn; //
    // pv(node->blue);pv(node->green);pn; // 
    // pn; /////

    for (int c = 'a'; c <= 'z'; ++c) {
        if (node->nxt[c - 'a'] == nullptr) {
            continue;
        }

        trieNode* urm = node->nxt[c - 'a'];
        trieNode* curr = node->blue;
        while (curr != root && curr->nxt[c - 'a'] == nullptr) {
            curr = curr->blue;
        }
        if (curr->nxt[c - 'a'] == nullptr || curr->nxt[c - 'a'] == urm) {
            urm->blue = root;
        }
        else {
            urm->blue = curr->nxt[c - 'a'];
        }

        build(urm, root);
    }
}

vector<int> solve(trieNode* root, const string& text, const int dictSize) {
    vector<int> occ(dictSize);

    trieNode* node = root;
    for (uint tidx = 0; tidx < text.size(); ++tidx) {
        int let = text[tidx] - 'a';        
        while (node != root && node->nxt[let] == nullptr) {
            node = node->blue;
        }
        node = (node->nxt[let] == nullptr) ? root : node->nxt[let];

        trieNode* curr = node;
        while (curr != root) {
            for (int idx : curr->wordIndex) {
                occ[idx] += 1;
            }
            curr = curr->green;
        }
    }

    return occ;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    string text;
    in >> text;
    int N;
    in >> N;
    for (int i = 0; i < N; ++i) {
        string word;
        in >> word;
        add(&root, word, 0, i);
    }

    build(&root, &root);

    vector<int> occ = solve(&root, text, N);
    for (int o : occ) {
        out << o << '\n';
    }

    return 0;
}