최장 공통 부분 수열(LCS)과 문자열(LCSubstring)

최장 공통 부분 수열(LCS: Longest Common Subsequence)

• 여러 수열(주로 문자열)중 순서를 유지하면서 공통으로 존재하는 가장 긴 부분 수열을 찾는다

  부분 수열

  • 문자열 일부를 건너뛰어도 되지만, 순서는 유지되어야 함

  예시

  • Git의 diff 유틸리티, 문서 비교 / 버전 관리, DNA 서열 분석

코드 리뷰

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[n][m]

print(lcs("ABCBDAB", "BDCAB"))  # 출력: 4

 

최장 공통 부분 문자열(LCSubstring: Longest Common Substring)

• 여러 문자열에서 연속적으로 일치하는 가장 긴 부분 문자열을 찾는다

  부분 문자열

  • 연속된 문자들의 묶음

  예시

  • 검색어 자동완성, 표절 탐지 도구, 키워드 일치 분석

코드 리뷰

def lcsubstring(a, b):
n, m = len(a), len(b)
dp = [[0] * (m+1) for _ in range(n+1)]
max_len = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            max_len = max(max_len, dp[i][j])
        else:
            dp[i][j] = 0  # 연속 조건이 깨짐

return max_len

print(lcsubstring("ABCDEF", "ZCDEK"))  # 출력: 3

차이점

항목	LCS (수열)	LCSubstring (문자열)
연속 여부	연속되지 않아도 됨	반드시 연속되어야 함
순서 유지	필요함	필요함
결과	가장 긴 공통 부분 수열	가장 긴 연속된 문자열
예시	ABCBDAB vs BDCAB → BCAB	ABCDEF vs ZCDEK → CDE

시간 복잡도

문자열과 수열(n은 첫번째, m은 두번째 문자열)

• O(n x m): 두 문자열을 비교하는 모든 경우의 수