LCS (최장 공통 부분 수열) 알고리즘 + 백준문제추천

사용언어

Visual studio 2019 C++

분류

DP(동적 프로그래밍)

이 알고리즘은 LIS (최장 증가 수열) 과 비슷하다.

LCS의 종류

Longest Common Substring : 공통 부분 문자열

s1: ABRACADABRA
s2: ECADADABRBCRDARA
result: ADABR (5)

int result = 0;
for (int i = 1; i <= s1.size(); i++) {
	for (int j = 1; j <= s2.size(); j++) {
		if (s1[i - 1] == s2[j - 1])
			arr[i][j] = arr[i - 1][j - 1] + 1;
		result = max(result, arr[i][j]);
	}
}

Longest Common Subsequence : 공통 부분 수열

s1: ABCDHEF
s2: BCDEF
-> BCDEF(5)

for (int i = 1; i <= s1.size(); i++) {
	for (int j = 1; j <= s2.size(); j++) {
		if (s1[i - 1] == s2[j - 1]) 
			arr[i][j] = arr[i - 1][j - 1] + 1;
		else 
			arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
	}
}
cout << arr[s1.size()][s2.size()] << endl;

백준문제

• Longest Common Substring

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

풀이: 5582 풀이

• Longest Common Subsequence

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

풀이: 9251 풀이

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

풀이: 9252 풀이

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

풀이: 1958 풀이

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

풀이: 13711 풀이

참조: https://mygumi.tistory.com/126