LCS ( Longest common substring, Longest Common subsequence)

1. 개요

이번에, LCS에 대해서 공부하게 되었다.

LCS의 의미가 2가지로 해석될 수 있다.

• Longest Common Substring
• Longest Common Subsequence

substring의 경우 연속된 문자 배열을 가지는 경우의 수를 의미하며, 

subsequence의 경우엔 연속되지 않더라도 공통된 문자 배열의 길이를 의미한다.

 

참고한 코드는 내가 사랑하는 geeks for geeks...

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

Longest Common Subsequence (LCS) - GeeksforGeeks

 

와 아래 블로그이다.

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

그림으로 아주 잘 설명되어 있어 이해하기가 좋았다.

 

2. 본론

Longest Common Substring의 경우, A[i], B[j] 가 동일한 문자를 나타낼 때, 1 + dp[i-1][j-1] 을 하는 것을 의미한다.

 

Longest Common subsequences는 이전에 찾은 동일한 문자 길이를 보존해 주어야 하기 때문에, Longest Common Substring 보다 조금 복잡하다.

만약, A[i]와 B[j]가 동일한 문자를 나타내지 않을 경우엔, max(dp[i-1][j], dp[i][j-1]) 을 통해 더 많이 연속된 배열의 길이를 받는다.

만약 동일한 문자를 나타낼 경우엔, 1 + dp[i-1][j-1]을 해주면 된다.

 

또한 연속된 문자들을 알아낼 수 있다.

Longest Common Substring의 경우, 최대 길이에서 부터 왼쪽 대각석 위로 한칸씩 0이 나올 때까지 옮겨주면 된다.

반면, Longest Common Subsequence의 경우,

처음엔 오른쪽 아래 모서리에서 시작한다. 만약, 위 혹은 왼쪽에 현재 위치의 길이와 동일한 길이가 있다면, 해당 숫자로 이동한다.

만약, 왼쪽과 위 둘다 동일한 길이를 나타낸다면, 한쪽으로 옮겨주면 된다. 단, 앞으로의 적용에 있어서 해당 규칙을 동일하게 적용해야 한다.

이후, 만약 인접한 숫자들이 현재 내가 있는 숫자와 동일하지 않다면, 왼쪽 위 대각석으로 옮겨주면 된다.

 

또한 대각석 이동 전 값을 stack에 저장해 준다. 숫자가 늘었다는 것은 연속된 숫자를 찾았다는 것을 의미하므로, 대각선 이동 전 값이 공통된 문자를 나타낸다고 판단한다.

 

이를 반복하고, stack에 저장한 값들을 순차적으로 pop을 하여 출력하면, 이것이 연속되는 문자 배열을 의미한다.

 

3. 코드

subsequence 말고, substring에 대한 코드를 스스로 작성해 보았다.

지피티가 아래 코드로 수정해 주었다.

def lcs(s1, s2, m, n, memo):
    # 기본 조건: 어느 한 문자열의 길이가 0이 되면 공통 부분 문자열은 존재하지 않음
    if m == 0 or n == 0:
        return 0

    # 이미 계산된 값이 있으면 바로 반환
    if memo[m][n] != -1:
        return memo[m][n]

    # 최대 공통 부분 문자열의 길이를 저장할 변수 (이 함수 내에서만 사용)
    max_len = 0

    # 두 문자가 같다면, 현재 위치에서 공통 부분 문자열의 길이를 1 증가
    if s1[m-1] == s2[n-1]:
        memo[m][n] = 1 + lcs(s1, s2, m-1, n-1, memo)
        max_len = memo[m][n]
    else:
        memo[m][n] = 0

    # 인접한 위치를 재귀적으로 탐색하면서 전체 최대 공통 부분 문자열 길이 갱신
    max_len = max(max_len, lcs(s1, s2, m-1, n, memo))  # 첫 번째 문자열의 이전 위치 탐색
    max_len = max(max_len, lcs(s1, s2, m, n-1, memo))  # 두 번째 문자열의 이전 위치 탐색

    return max_len  # 전체 최대 길이 반환

 

max_len에 대한 처리를 해주었다.

뭔가 코드가 맘에 들지 않아서, geeks for geeks에서 longest common substring에 대한 코드를 확인해 보았다.

https://www.geeksforgeeks.org/longest-common-substring-dp-29/

Longest Common Substring - GeeksforGeeks

역시.. 짱스폴긱스..