BOJ2020 부분 염기서열

 

2020번 부분 염기서열

주어진 염기서열을 문자열로 볼 때, 문자열의 모든 부분 문자열에 대해

m번 이상 나타나는 부분 문자열의 개수를 구하고

1)길이 2)사전식 으로 나열했을 때 k번째의 부분 문자열을 구한다.

 

 

두 가지 방법이 있다.

1. BFS

2. Suffix, Prefix 활용

두 방법 모두 길이 순으로 부분 문자열을 찾는다는 게 그나마의 공통점인 듯

 

---

1. BFS

길이가 len인 어떤 문자열 s가 m번 이상 등장한 경우

문자열 s를 prefix로 하고 길이가 len+1인 문자열 s'를 찾아 탐색하면서

길이가 짧은 순으로 문자열을 탐색할 수 있다.

 

아래 두 자료구조를 사용한다.

queue<vector<int>> Q; 
map<char, vector<int>> M;

 

먼저 길이가 1인 부분 문자열을 찾아야 한다.

	for (int i = 0; i < n; i++) M[str[i]].push_back(i);
	for (auto it = M.begin(); it != M.end(); it++)
		if((it->second).size() >= m) Q.push(it->second);

각 문자열의 문자를 key로 하고

문자가 등장한 위치를 key에 해당하는 value 벡터에 삽입한 뒤

이 벡터 중 크기가 m이상인 벡터만 모두 Q에 삽입한다.

즉 초기 상태에서 Q에는 같은 문자가 나타난 위치를 저장한 벡터가 저장되는 것

 

 

이제 BFS로 길이를 늘려가며 문자열을 찾는다.

	string ans;
	int cnt = 0, len = 1, qsize = Q.size();
	while (qsize) {
		while(qsize--) {
			vector<int> V = Q.front(); Q.pop(); cnt++;
			if (cnt == k) ans = str.substr(V[0], len);

			M.clear();
			for (int v : V) {
				if (v + len >= n) break;
				M[str[v + len]].push_back(v);
			}
			for (auto it = M.begin(); it != M.end(); it++)
				if((it->second).size() >= m) Q.push(it->second);
		}
		len++; qsize = Q.size();
	}

line 5

Q.front()인 벡터 V는 길이가 len인 어떤 부분 문자열에 대해

동일한 부분 문자열이 등장한 위치(첫 번째 index)를 모두 저장한 벡터이다.

따라서 V의 모든 원소 v에 대해 str.substr(v,len)은 동일한 부분 문자열,

V의 크기는 str에서 str.substr(v,len)의 등장 횟수를 의미한다.

이미 m 이상 크기의 벡터만 Q에 push했으므로 cnt를 늘린다.

 

line 6

m번 이상 등장한 부분 문자열 중 k번째 문자열을 찾는다.

map의 key는 사전식으로 정렬되며, 현재 BFS를 len을 늘려가며 해주고 있기 때문에

BFS상 k번째로 찾은 문자열이 정답의 문자열이다.

 

line 8~14

str.substr(v,len)을 prefix로 하고 길이가 len+1인 문자열을 모두 찾아 조사한 뒤

찾은 문자열에 대한 벡터 중 크기가 m 이상인 것만 Q에 삽입한다.

 

line 4~15가 끝나면 len을 1 증가, qsize를 바꿔주고

다시 길이 len에 대한 모든 부분 문자열에 대해 탐색한다. 

 

 

str=ACACATGACT m=2인 경우

M = { { 'A', {0,2,4,7} }, { 'C', {1,3,8} }, { 'G', {6} }, { 'T', {5,9} } }, Q에 {0,2,4,7}, {1,3,8}, {5,9} push

 

len=1, qsize=3

V={0,2,4,7} A ⇒ cnt=1, M = { { 'C', {0,2,7} }, { 'T', [4} } }, Q에 {0,2,7} push

V={1,3,8} C ⇒ cnt=2, M = { { 'A', {1,3} }, { 'T', {8} } }, Q에 {1,3} push

V={5,9} T ⇒ cnt=3, M = { { 'G', {5} } }

 

len=2, qsize=2

V={0,2,7} AC ⇒ cnt=4, M = { { 'A', {0,2} }, { 'T', {7} } }, Q에 {0,2} push

V={1,3} CA ⇒ cnt=5, M = { { 'C', {1} } { 'T', {3} } }

 

len=3, qsize=1

V={0,2} ACA ⇒ cnt=6, M={ { 'C', {0} }, { 'T', {2} } }

 

len=4, qszie=0으로 종료한다.

 

이렇게 찾으면 str에서 2번 이상 등장한 문자열을 A, C, T, AC, CA, ACA 순으로 찾을 수 있다.

 

 

---

2. Suffix, Prefix 활용

문자열 str의 모든 suffix를 찾은 뒤 각 suffix간 동일한 prefix를 찾는 방식이다.

서로 다른 suffix간 동일한 prefix가 존재하려면 문자열 str내에서 여러 번 등장해야 한다.

 

 

이때 문자열 자체가 아닌 문자열이 시작하는 위치와 길이로 문자열을 나타내기 때문에 아래 정렬방식을 이용한다.

bool sortstr(int A, int B) {
	return str.substr(A) < str.substr(B);
}
bool sortstr2(const pii& A, const pii& B) {
	return str.substr(A.first, A.second) < str.substr(B.first, B.second);
}

 

 

먼저 str의 모든 suffix를 찾아 벡터 S에 저장하고 사전식으로 정렬한다.

	vector<int> S(n);
	for (int i = 0; i < n; ++i)	S[i] = i;
	sort(S.begin(), S.end(), sortstr);

 

 

suffix간 겹치는 prefix가 있는지 조사한다.

	vector<pair<int,int>> V;
	for (int i = 0; i + m - 1 < n; ++i) {
		int len = 0, a = S[i], b = S[i + m - 1];
		while (a < n && b < n && str[a] == str[b]) ++len, ++a, ++b;
		if (len) V.push_back({ S[i], len });
	}
	sort(V.begin(), V.end(), sortstr2);

suffix S[a]와 suffix S[b]의 공통 prefix를 찾아 벡터 V에 {첫 번째 인덱스, 길이}로 삽입한다.

S[a]와 S[b]가 공통 prefix를 가진다면

그 사이에 있는 모든 suffix(S[a+1], S[a+1], ... , S[b-1]) 또한 같은 prefix를 가진다. ∴ b-a=m-1으로 한다.

 

벡터 V는 m번 이상 등장하는 부분 문자열을 모두 포함하진 않지만

해당 문자열 중 길이가 가장 긴 문자열은 모두 포함한 상태이다.

예를 들어 V의 원소에 ACGC가 있다면 A, AC, ACG, ACGC 모두 m번 이상 등장하는 부분 문자열인 것

 

벡터 V를 다시 사전식으로 정렬한다.

 

 

이제 길이를 for문으로 늘려가며 k번째 문자열을 찾는다.

	bool chk[1001] = { false, };
	int cnt = 0, vsize = V.size();
	string ans;
	for (int len = 0; len < n; ++len) {
		for (int j = 0; j < vsize; ++j) {
			if (len >= V[j].second) continue;
			if (!chk[j] && j > 0 && len < V[j - 1].second
				&& str[V[j].first + len] == str[V[j - 1].first + len]) continue;

			chk[j] = true, ++cnt;
			if (cnt == k) ans = str.substr(V[j].first, len + 1);
		}
	}

line 6

V의 원소는 {부분 문자열의 첫 번째 인덱스, 길이} 였다. 길이가 len보다 작으면 문자열을 찾을 수 없으므로 continue

 

line 7~8

* chk[j]는 str.substr(V[j],len+1)인 문자열을 이미 찾았는지 판단한다.

str.substr(V[j].first,len)을 탐색하지 않은 부분 문자열 V[j]에 대해

V[j-1]와 공통 prefix길이가 len+1이상이면 continue

이 문자열은 이미 V[j-1]에서 탐색되었기 때문이다.

 

line 10~11

위 조건문을 거친 문자열 str.substr(V[j],len+1)은 사전식에 맞게 새로 찾은 부분 문자열이다.

문자열의 개수를 세고 k번째 문자열을 찾는다.

 

 

 

 

str=ACACATGACT m=2인 경우

 

suffix를 찾아 사전순으로 배열하면

0 ACACATGACT

2 ACATGACT
7 ACT
4 ATGACT
1 CACATGACT
3 CATGACT
8 CT
6 GACT
9 T
5 TGACT ⇒ S = { 0,2,7,4,1,3,8,6,9,5 }

 

S[0], S[1]비교, S[1], S[2]비교, ... 로 V의 원소를 찾으면

V={ {7,1}, {2,2}, {0,3}, {3,1}, {1,2}, {9,1} } ≒ { A, AC, ACA, C, CA, T }

 

len=0

{7,1}에서 A

{3,1}에서 C

{9,1}에서 T

{2,2}, {0,3}, {1,2}는 두 번째 조건문에 의해 continue

 

len=1

{2,2}에서 AC

{1,2}에서 CA

길이가 1인 경우 첫 번째 조건문에 의해, {0,3}은 두 번째 조건문에 의해 continue

 

len=2

{0,3}에서 ACA

 

따라서 str에서 2번 이상 등장한 문자열을 A, C, T, AC, CA, ACA 순으로 찾을 수 있다.

 

 

 

사실 문제 태그에는 해싱이라고 되어있는데 어떤 방식을 생각하고 쓴 건지는 잘 모르겠다.

두 가지 방법 모두 너무 어려웠고 특히 두 번째 방법은 이해하는 데 꽤나 걸렸던