Algorithm) 최장 공통 부분 수열(Longest Common Subsequence) c++

DP 문제를 풀다가 만나게 된 친구입니다

BCD처럼 연속된 것만 찾는다면 최장 공통 문자열

BCDF, BCDE처럼 연속되지 않아도 된다면 최장 공통 부분 수열입니다

 

최장 공통 문자열의 점화식은 요렇고

if(i==0 || j==0) {
	LCS[i][j] = 0;
 } else if( A[i] == B[j]) {
 	LCS[i][j] = LCS[i-1][j-1] + 1;
 } else {
 	LCS[i][j] = 0;
 }

최장 공통 부분 수열의 점화식은 이렇습니다

if(i==0 || j==0) {
	LCS[i][j] = 0;
 } else if( A[i] == B[j]) {
 	LCS[i][j] = LCS[i-1][j-1] + 1;
 } else {
 	LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]_;
 }

둘의 차이는 꼭 연속되지 않음에서 비롯됩니다

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

이 글 보시면 쉽게 이해할 수 있으실거에요!