LCS (Longest Common Subsequence)
-
LCS(Longest Common Subsequence) 알고리즘은 두 문자열(또는 두 시퀀스)에서 가장 긴 공통 서브시퀀스를 찾는 것이 목적이다.
-
공통 서브스트링을 찾는 것이 목적이 아니다.
-
subsequence는 substring을 커버하는 더 넓은 범주이다.
서브스트링 (Substring) 과 서브시퀀스 (Subsequence)
서브스트링 (Substring): 문자열에서 연속된 일련의 문자들로 이루어져 있어야 합니다. 예를 들어, "apple"이라는 문자열에서 "ppl"은 서브스트링입니다.
서브시퀀스 (Subsequence): 문자열에서 연속되지 않을 수도 있는 일련의 문자들로 이루어져 있습니다. 예를 들어, "apple"에서 "apl"은 서브시퀀스입니다. 이는 원래 문자열에서 'a', 'p', 'l'이라는 문자들이 등장하면서 순서가 유지되기 때문입니다. 이 문자들은 연속적이지 않아도 됩니다.
