[BOJ 10256] 돌연변이

 

[문제] 

 

www.acmicpc.net/problem/10256

10256번: 돌연변이

 

[난이도]

 

- Platinum 3 (solved.ac 20.12.11 기준)

 

 

[필요 개념]

 

- 아호코라식 (Aho-corasick)

 

 

[풀이]

 

마커(marker)의 돌연변이의 경우의 수는 최대 $m^2$이다. 

m이 100이하이므로 모든 돌연변이를 직접 다 만들어도 무리가 없다.

그리고, 만들어진 돌연변이들을 트라이에 넣어두고, DNA문자열을 탐색한다. 

이때, 모든 돌연변이들의 길이가 같기 때문에 단순하게 DNA문자열의 각 index에서 끝나는 돌연변이가 있는지를 체크하고, 있다면 ans++만 해주면 충분하다.

돌연변이들은 중복되지 않기 때문에 각 index별로 일치하는 돌연변이가 최대 1개이기 때문이다.

 

만약 돌연변이들의 길이가 서로 다르다면, 각 index별로 일치하는 돌연변이들의 개수만큼 ans에 더해줘야 한다.

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
int ans;
int tonum(char c) {
	if (c == 'A') return 0;
	else if (c == 'G') return 1;
	else if (c == 'T') return 2;
	else return 3;
}
struct Trie {
	Trie* ch[4];
	bool end;
	Trie* fail;
	Trie() {
		fill(ch, ch + 4, nullptr);
		end = 0;
		fail = nullptr;
	}
	~Trie() {
		for (int i = 0; i < 4; i++) if (ch[i]) delete ch[i];
	}
	void insert(const char* s) {
		if (!*s) {
			end = true;
			return;
		}
		int now = tonum(*s);
		if (!ch[now]) ch[now] = new Trie;
		ch[now]->insert(s + 1);
	}
	void init() {
		queue<Trie*>q;
		q.push(this);
		while (!q.empty()) {
			Trie* now = q.front(); q.pop();
			for (int i = 0; i < 4; i++) {
				Trie* next = now->ch[i];
				if (!next) continue;
				if (now == this) next->fail = this;
				else {
					Trie* t = now->fail;
					while (t != this && !t->ch[i]) t = t->fail;
					if (t->ch[i]) t = t->ch[i];
					next->fail = t;
				}
				if (next->fail->end) next->end = true;
				q.push(next);
			}
		}
	}
	void query(const string& s) {
		Trie* cur = this;
		for (int i = 0; i < sz(s); i++) {
			int now = tonum(s[i]);
			while (cur != this && !(cur->ch[now])) cur = cur->fail;
			if (cur->ch[now]) cur = cur->ch[now];
			if (cur->end) ans++;
		}
	}
};
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int n, m; cin >> n >> m;
		string a, b; cin >> a >> b;
		Trie* root = new Trie;
		ans = 0;
		root->insert(b.c_str());
		for (int i = 0; i < sz(b); i++) {
			for (int j = i + 1; j < sz(b); j++) {
				string tmp = b;
				reverse(tmp.begin() + i, tmp.begin() + j + 1);
				root->insert(tmp.c_str());
			}
		}
		root->init();
		root->query(a);
		cout << ans << '\n'; 
		delete root;
	}
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^