[BOJ] 10256 돌연변이

문제: https://www.acmicpc.net/problem/10256

 

 

문제 풀이:

아호코라식 알고리즘을 이용한다.

1. 주어진 마커를 뒤집어서 나올 수 있는 모든 문자열을 trie에 넣는다

2. DNA 문자열을 root부터 대입 시키면서 마커의 끝을 만나면 res에 더해준다

 

 

소스 코드:

#include <iostream>
#include <queue>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;


int tc, n, m;
char str1[1000002], str2[102];

struct trie {
	trie *next[4];
	trie *fail;
	int finish;

	trie() {
		fill(next, next + 4, nullptr);
		finish = 0;
	}
	~trie() {
		for (int i = 0; i < 4; i++) {
			if (next[i]) delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = 1;
			return;
		}
		int word;
		if (*key == 'A') word = 0;
		else if (*key == 'G') word = 1;
		else if (*key == 'T') word = 2;
		else word = 3;

		if (!next[word]) next[word] = new trie();
		next[word]->insert(key + 1);
	}
};  


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		trie* root = new trie;
		cin >> n>>m;
		cin >> str1 >> str2;
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j <= m; j++) {
				reverse(str2+i,str2+j);
				root->insert(str2);
				reverse(str2 + i, str2 + j);
			}
		}


		// BFS를 통해 트라이 노드를 방문하여 fail 함수를 만든다.
		queue<trie*> q;
		root->fail = root;
		q.push(root);
		while (!q.empty()) {
			trie* cur = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {
				trie *next = cur->next[i];
				if (!next) continue;

				if (cur == root) next->fail = root;
				else {
					trie *dest = cur->fail;

					//fail을 참조할 가장 가까운 조상을 찾아간다
					while (dest != root && !dest->next[i]) {
						dest = dest->fail;
					}
					//fail(px)=go(fail(p),x)
					if (dest->next[i]) dest = dest->next[i];
					next->fail = dest;
				}
				
				q.push(next);
			}
		}

		trie* cur = root;
		int res = 0;
		for (int c = 0; str1[c]; c++) {
			int next;
			if(str1[c]=='A') next=0;
			else if(str1[c]=='G') next=1;
			else if(str1[c]=='T') next=2;
			else next=3;

			//현재 노드에서 갈 수 없으면 fail을 계속 따라감
			while (cur != root && !cur->next[next]) {
				cur = cur->fail;
			}
			// next 함수가 존재하면 이동. 루트면 이게 false일 수도 있다.
			if (cur->next[next]) cur = cur->next[next];

			//현재 노드에 finish가 있으면 찾은 것이다.
			if (cur->finish) {
				res += cur->finish;
			}
		}
		cout << res << '\n';
		delete root;
	}
	

	return 0;
}