Cod sursa(job #2606226)

Utilizator radustn92Radu Stancu radustn92 Data 27 aprilie 2020 12:39:37
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 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;
}