#6 LCS 알고리즘

 LCS 알고리즘은 최장 공통 부분 수열(Longest Common Subsequence)과 최장 공통 부분 문자열(Longest Common Substring) 두 종류가 있다.  최장 공통 부분 수열은 공통부분의 원소가 연속이 아니어도 상관없지만 최장 공통 부분 문자열은 공통부분의 원소가 연속이어야 한다.

 

1. 최장 공통 부분 수열(Longest Common Subsequence)

 LCS 문제는 기본적으로 DP(Dynamic Programming)문제이다.  절차는 다음과 같다. 

1. 문자열 A와 B의 길이가 각각 N, M 일때,  (N+1) * (M+1) 크기의 배열 dp를 생성(메모이제이션을 위한 배열)

 

2. 1 <= i <= N ,  1 <= j <= M 인 i, j에 대해

   ① A[i-1] == B[j-1] 라면 dp[i][j] = dp[i-1][j-1] + 1

   ② A[i-1] != B[j-1] 라면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

3. 최장 공통 부분 수열의 길이는 dp[N][M]

 

4. 실제 최장 공통 부분 수열을 담기 위한 배열 lcs를 생성

 

5. i=N, j=M 에서 시작

   ① A[i-1] == b[j-1] 이라면 lcs에 A[i-1] 추가, i -= 1,  j -= 1

   ② A[i-1] != b[j-1] 이고 dp[i][j-1] > dp[i-1][j] 라면 j -= 1

   ③ A[i-1] != b[j-1] 이고 dp[i][j-1] <= dp[i-1][j] 라면 i -= 1

 

6. lcs 뒤집기

 

3번 까지의 절차만 수행하면 LCS의 길이를 구할 수 있고 6번까지 수행하면 LCS를 직접 구할 수 있다.

아래는 위 절차에 따라 LCS 문제(https://www.acmicpc.net/problem/9252)를 해결한 코드이다. 

import sys


def sol9252(s1, s2):
    # 1
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

    # 2
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    # 3
    l = str(dp[-1][-1])

    # 4
    lcs = []

    # 5
    i, j = len(s1), len(s2)
    while dp[i][j]:
        if s1[i - 1] == s2[j - 1]:
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
        else:
            if dp[i][j - 1] > dp[i - 1][j]:
                j -= 1
            else:
                i -= 1
    
    # 6
    lcs.reverse()

    return '\n'.join((l, ''.join(lcs)))


if __name__ == '__main__':
    input = sys.stdin.read
    str1, str2 = input().split()
    print(sol9252(str1, str2))

 

 

 

2. 최장 공통 부분 문자열(Longest Common Substring)

 최장 공통 부분 문자열을 구하는 것은 최장 공통 부분 수열을 구하는것과 거의 유사하다. 절차는 다음과 같다.

1. 문자열 A와 B의 길이가 각각 N, M 일때,  (N+1) * (M+1) 크기의 배열 dp(메모이제이션을 위한 배열)와

   최장 공통 부분 문자열의 길이를 계산하기 위한 lcslen(= 0), 인덱스인 lcsi, lcsj 를 선언

 

2. 1 <= i <= N ,  1 <= j <= M 인 i, j에 대해 A[i-1] == B[j-1]일 경우

   ① dp[i][j] = dp[i-1][j-1] + 1

   ② dp[i][j] 가 lcslen 보다 크다면 lcslen = dp[i][j],  lcsi = i, lcsj = j

 

3. 최장 공통 부분 문자열의 길이는 lcslen

 

4. 실제 최장 공통 부분 문자열을 담기 위한 배열 lcs를 생성

 

5. i=lcsi, j=lcsj 에서 시작하여 dp[i][j]가 0이 아닐 때 까지 lcs에 A[i-1] 추가, i -= 1, j -= 1

 

6. lcs 뒤집기

 

마찬가지로 3번 까지의 절차만 수행하면 LCS의 길이를 구할 수 있고 6번까지 수행하면 LCS를 직접 구할 수 있다.

아래는 위 절차에 따라 LCS 문제(https://www.acmicpc.net/problem/5582)를 해결한 코드이다.  원래 문제에서는 LCS의 길이만을 구하지만 여기서는 제출한 것에서 코드를 조금 변형하여 LCS자체도 구하였다.  파이썬은 시간, 메모리 조건이 상당히 아슬아슬하기 때문에 실제로 위 문제를 해결하려면 dp배열을 N * M이 아니라 N * 2 로 제한하여 재활용하는 형태로 제출해야했다.

import sys

input = sys.stdin.read


def sol5582():
    a, b = input().split()
    # 1
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    lcslen, lcsi, lcsj = 0, 0, 0
    
    # 2
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > lcslen:
                    lcslen, lcsi, lcsj = dp[i][j], i, j

	# 3
    l = str(lcslen)
    
    # 4
    lcs = []
    
    # 5
    while dp[lcsi][lcsj]:
        lcs.append(a[lcsi-1])
        lcsi -= 1
        lcsj -= 1
       
    # 6   
    return '\n'.join((str(lcslen), ''.join(lcs[::-1])))


if __name__ == '__main__':
    print(sol5582())