아호코라식. [10256]

 

 

 

 

[코드]

	#include <iostream>
	#include <string>
	#include <algorithm>
	#include <vector>
	#include <queue>
	#include <cstring>
	int mapping[26];
	// 트라이 자료구조에서
	// 모든 대문자 알파벳을 처리하도록 하는 것이 시간 초과 원인
	// bfs 및 delete 과정에서 오래 걸림.
	//
	// 마커의 모든 패턴을 다 만들어도 5050 개 밖에 안되므로,
	// 모든 패턴을 만드는 것은 시간초과가 아님.
	struct trie {
	int terminal;
	trie * children[4];
	trie * fail;
	std::vector<int> output;
	trie() {
	terminal = -1;
	fail = nullptr;
	output.clear();
	for (int i=0; i<4; i++) {
	children[i] = nullptr;
	}
	}
	~trie() {
	for (int i=0; i<4; i++) {
	delete children[i];
	}
	}
	void insert(const std::string &st, const int cur, const int idx) {
	if (cur >= st.size()) {
	terminal = idx;
	return;
	}
	const int it = mapping[st[cur] - 'A'];
	if (children[it] == nullptr) {
	children[it] = new trie;
	}
	children[it]->insert(st, cur+1, idx);
	}
	};
	void computeFail(trie * root)
	{
	std::queue<trie*> q;
	root->fail = root;
	q.push(root);
	while (q.size() > 0) {
	trie * here = q.front();
	q.pop();
	// visit child
	for (int i=0; i<4; i++) {
	trie * child = here->children[i];
	if (child == nullptr) {
	continue;
	}
	if (here == root) {
	child->fail = root;
	} else {
	trie * t = here->fail;
	while (t != root && t->children[i] == nullptr) {
	t = t->fail;
	}
	if (t->children[i]) {
	t = t->children[i];
	}
	child->fail = t;
	}
	child->output = child->fail->output;
	if (child->terminal != -1) {
	child->output.push_back(child->terminal);
	}
	q.push(child);
	}
	}
	}
	int search(const std::string &dna, const trie * root)
	{
	int result = 0;
	const trie * state = root;
	for (int i=0; i<dna.size(); i++) {
	const int it = mapping[dna[i] - 'A'];
	while (state != root && state->children[it] == nullptr) {
	state = state->fail;
	}
	if (state->children[it]) {
	state = state->children[it];
	}
	result += state->output.size();
	}
	return result;
	}
	int solve(const std::string &dna, const std::string &marker)
	{
	const int len = marker.size();
	trie * root = new trie;
	int k =0 ;
	// 여기서 시간초과 일 듯..
	for (int f=0; f<=len; f++) {
	const std::string str0 = marker.substr(0, f);
	for (int s=1; f+s<=len; s++) {
	if (f+s < f) break;
	// [f..f+s)
	std::string str1 = marker.substr(f, s);
	std::reverse(str1.begin(), str1.end());
	for (int t=0; f+s+t<=len; t++) {
	if (f+s+t < f+s) break;
	if (f+s+t < len) continue;
	// [f+s, f+s+t)
	const std::string str2 = marker.substr(f+s, t);
	const std::string test = str0+str1+str2;
	root->insert(test, 0, k++);
	}
	}
	}
	computeFail(root);
	const int result = search(dna, root);
	delete root;
	return result;
	}
	int main()
	{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int TC;
	std::cin >> TC;
	memset(mapping, 0, sizeof(mapping));
	mapping['A' - 'A'] = 0;
	mapping['G' - 'A'] = 1;
	mapping['T' - 'A'] = 2;
	mapping['C' - 'A'] = 3;
	for (int t=0; t<TC; t++) {
	int a, b;
	std::string dna;
	std::string marker;
	std::cin >> a >> b;
	std::cin >> dna >> marker;
	const int result = solve(dna, marker);
	std::cout << result << "\n";
	}
	return 0;
	}

view raw 10256.cpp hosted with ❤ by GitHub