개발하는데 다 이유가 있겠지

LCS(Longest Common Subsequence)

• 최장 공통 부분수열(Longest Common Subsequence) : BCDF 또는 BCDE
• 최장 공통 문자열(Longest Common Substring) : BCD

→ F, E는 문자열을 건너뛰기 때문에 문자열로 인식하지 않음

 

점화식

if i == 0 or j == 0:  # 마진 설정
    LCS[i][j] = 0
elif string_A[i] == string_B[j]:
    # 문자열 앞에까지만 비교하고 마지막 끝에 값이 같으니 +1
    LCS[i][j] = LCS[i - 1][j - 1] + 1 
else:
    LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

 

1. LCS[i - 1][j]와 LCS[i][j - 1]는 어떤 의미인가?

부분수열은 연속된 값이 아닙니다.** 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지됩니다. '현재의 문자를 비교하는 과정' 이전의 과정이 바로 LCS[i - 1][j]와 LCS[i][j - 1]가 됩니다.

문자열 AB와 GBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠습니다. AB와 GBC의 최대 공통 부분수열이 B라는 것을 알기 위해서는 문자열 A와 GBC를 비교하는 과정, 문자열 AB와 GB를 비교하는 과정이 필요합니다. 문자열 AB와 GB의 비교 과정에서 최대 공통 부분수열이 B임을 확인했기 때문에 문자열 AB와 GBC의 최대 공통 부분수열 역시 B가 되는 것입니다.

 

2. 왜 문자가 같으면 LCS[i][j] = LCS[i - 1][j - 1] + 1인가?

최대 공통 문자열을 구할 때 비교하는 문자가 같으면 LCS[i][j] = LCS[i - 1][j - 1] + 1의 과정을 거쳤습니다. 이 과정이 어떻게 최대 공통 부분수열에도 똑같이 적용될까요? 부분수열이 연속될 필요가 없음을 위 과정에서 여러번 보았습니다. 그렇다면 답은 간단합니다. 두 문자가 같은 상황이 오면 지금까지의 최대 공통 부분수열에 1을 더해주는 것 입니다.

문자열 ABC와 GBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠습니다. LCS 배열은 LCS[i - 1][j]와 LCS[i][j - 1]의 비교를 통해 언제나 본인까지의 최대 공통 부분수열 값을 가지고 있습니다. 문자열 AB와 GB를 비교할때와 문자열 ABC와 GBC를 비교할 때 달라진 점은 두 문자열 모두에 C가 추가된 점입니다. 때문에 기존의 최대 공통 부분수열인 B에 C를 더한 BC가 최대 공통 부분수열이 되는 것입니다.

 

글씨 너무 못쓴다..

[출처]

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