Cod sursa(job #2606210)

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

	node* next[LMAX];

	node* link;

	int cntText;

	node() {
		fill(begin(next), end(next), nullptr);
		link = nullptr;
	}
};
node* root = new node();

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

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

void bfsAndComputeSuffixLink() {
	root -> link = root;

	queue<node*> nodes;
	nodes.push(root);
	while (!nodes.empty()) {
		node* currNode = nodes.front();
		nodes.pop();
		sortedNodes.push_back(currNode);

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

				node* nextNode = currNode -> next[idx];
				if (currNode == root) {
					nextNode -> link = root;
				} else {
					node* suffixLink = currNode -> link;
					while (suffixLink != root && suffixLink -> next[idx] == NULL) {
						suffixLink = suffixLink -> link;
					}
					nextNode -> link = (suffixLink -> next[idx] != NULL) ? suffixLink -> next[idx] : root;
				}				
			}
		}
	}
}

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

		currNode -> cntText++;
	}
}

void ansQueries() {
	for (auto it = sortedNodes.rbegin(); it != sortedNodes.rend(); it++) {
		node* currNode = *it;
		(currNode -> link) -> cntText += currNode -> cntText;

		for (auto wordIdx : currNode -> endInNode) {
			ans[wordIdx] = 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;
}