Longest Common Substring

LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

Longest Common Subsequence? Substring? LCS는 주로 최장 공통 부분수열(Longest Common Subsequence) 또는, 최장 공통 문자열(Longest Common Substring)을 뜻한다. 해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다. 최장 공통 문자열(Longest Common Substring) 최장 공통 부분수열(Longest Common Subse..