LCS

1. Longest Common Substring

---

두 문자열 사이에서 연속적으로 공통된 문자 중 가장 긴 문자열 찾기 (최장 공통 문자열)

 

과정

• 2차원 배열을 통해서 하나씩 비교하면서
• 두 문자가 다르면 dp[i][j] = 0
• 같은 문자가 나온 순간 dp[i][j] = dp[i-1][j-1] + 1

아래와 같은 표의 형태로 dp 배열을 구성할 수 있다

	-	A	B	C	D	E	F
-	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0
C	0	0	0	2	0	0	0
D	0	0	0	0	3	0	0
F	0	0	0	0	0	0	1
E	0	0	0	0	0	1	0

 

결론적으로 최장 공통 문자열의 길이는 3이 된다.

 

 

2. Longest Common Subsequence

---

최장 공통 "부분수열" -> 중간에 끊기더라도 부분수열로서 연속된 문자열을 찾기

 

과정

• 2차원 배열을 통해서 하나씩 비교하기
• 두 문자가 다르면 dp[i - 1][j] 와 dp[i][j - 1] 중 큰 값 선택
• 두 문자가 같으면 dp[i - 1][j - 1] + 1

	-	A	B	C	D	E	F
-	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1
C	0	0	1	2	2	2	2
D	0	0	1	2	3	3	3
F	0	0	1	2	3	3	4
E	0	0	1	2	3	4	4

 

결론적으로 정답은 4가 된다.

 

 

3. LCS 문자열 찾기

---

위의 문제에서는 길이를 찾는 것에 집중하였고, 이번에는 실제로 문자열을 찾기 방법을 알아보자

 

과정

• 위에서 구한 배열을 먼저 구한 후 배열의 가장 마지막 값에서 시작하여 dp[i - 1][j] 또는 dp[i][j - 1] 중 같은 값을 찾는다.
• 같은 값이 있는 경우 해당 방향으로 이동
• 같은 값이 없는 경우 dp[i - 1][j - 1] 로 이동 후 dp[i][j]의 값을 결과 문자열에 넣는다.
• dp[i][j]의 값이 0이 되는 경우 마무리하면 된다.

아래 그림의 경우 FDCB 가 찍히기 때문에 이 문자를 뒤집어서 BCDF가 정답이 된다.

 

 

4. 실습 코드

---

LCS 문제

https://www.acmicpc.net/problem/9251

#include <iostream>
using namespace std;

string str1;
string str2;
int dp[1002][1002];
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> str1 >> str2;

	for (int i = 1; i <= str1.size(); ++i)
	{
		for (int j = 1; j <= str2.size(); ++j)
		{
			if (str1[i - 1] == str2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;

			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);			
			answer = max(answer, dp[i][j]);
		}
	}
	cout << answer;
}

 

LCS 문자열 구하는 문제

https://www.acmicpc.net/problem/9252

#include <iostream>
#include <algorithm>
using namespace std;

string str1;
string str2;
string ans;
int dp[1002][1002];
int answer = 0;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> str1 >> str2;

	for (int i = 1; i <= str1.size(); ++i)
	{
		for (int j = 1; j <= str2.size(); ++j)
		{
			if (str1[i - 1] == str2[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;

			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			answer = max(answer, dp[i][j]);
		}
	}
	
	int x = str1.size();
	int y = str2.size();
	
	while (dp[x][y] != 0)
	{
		if (dp[x][y] == dp[x][y - 1])
			y--;
		else if (dp[x][y] == dp[x - 1][y])
			x--;
		else
		{
			ans += str1[x-1];
			x--;
			y--;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << answer << "\n" << ans;
}