Cod sursa(job #2606228)

Utilizator radustn92Radu Stancu radustn92 Data 27 aprilie 2020 12:40:25
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.08 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX = 105;
const int LMAX = 26;

struct node {
    vector<int> endInNode;

    int next[LMAX];

    int link;

    int cntText;

    node() {
        fill(begin(next), end(next), -1);
        link = -1;
        cntText = 0;
    }
};
vector<node> nodesList(1);

const int ROOT = 0;

string text;
int N, ans[NMAX];
string words[NMAX];
vector<int> sortedNodes;

void insertWord(int currNode, string& word, int idx) {
    for (size_t idx = 0; idx < word.size(); idx++) {
        int chIdx = word[idx] - 'a';
        if (nodesList[currNode].next[chIdx] == -1) {
            nodesList[currNode].next[chIdx] = nodesList.size();
            nodesList.emplace_back();
        }
        currNode = nodesList[currNode].next[chIdx];
    }
    nodesList[currNode].endInNode.push_back(idx);
}

void bfsAndComputeSuffixLink() {
    nodesList[ROOT].link = ROOT;

    queue<int> nodes;
    nodes.push(ROOT);
    while (!nodes.empty()) {
        int currNode = nodes.front();
        nodes.pop();
        sortedNodes.push_back(currNode);

        for (int idx = 0; idx < LMAX; idx++) {
            if (nodesList[currNode].next[idx] != -1) {
                int nextNode = nodesList[currNode].next[idx];
                nodes.push(nextNode);

                if (currNode == ROOT) {
                    nodesList[nextNode].link = ROOT;
                } else {
                    int suffixLink = nodesList[currNode].link;
                    while (suffixLink != ROOT && nodesList[suffixLink].next[idx] == -1) {
                        suffixLink = nodesList[suffixLink].link;
                    }
                    nodesList[nextNode].link = nodesList[suffixLink].next[idx] != -1 ? nodesList[suffixLink].next[idx] : ROOT;
                }               
            }
        }
    }
}

void processText(string& text) {
    int currNode = ROOT;
    for (size_t idx = 0; idx < text.size(); idx++) {
        int chIdx = text[idx] - 'a';
        while (currNode != ROOT && nodesList[currNode].next[chIdx] == -1) {
            currNode = nodesList[currNode].link;
        }
        currNode = (nodesList[currNode].next[chIdx] != -1) ? nodesList[currNode].next[chIdx] : ROOT;

        nodesList[currNode].cntText++;
    }
}

void ansQueries() {
    for (auto it = sortedNodes.rbegin(); it != sortedNodes.rend(); it++) {
        int currNode = *it;
        nodesList[nodesList[currNode].link].cntText += nodesList[currNode].cntText;

        for (auto wordIdx : nodesList[currNode].endInNode) {
            ans[wordIdx] = nodesList[currNode].cntText;
        }
    }

    for (int idx = 0; idx < N; idx++) {
        cout << ans[idx] << "\n";
    }
}

int main() {
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> text;
    cin >> N;
    for (int idx = 0; idx < N; idx++) {
        cin >> words[idx];
        insertWord(ROOT, words[idx], idx);
    }

    bfsAndComputeSuffixLink();
    processText(text);
    ansQueries();
    return 0;
}