[컴퓨터알고리즘] LCS 알고리즘 구현

1. LCS 알고리즘 설명

어떤 두 문자열이 얼마나 유사한지를 수치화하기 위해 longest common subsequence(LCS)를 구한다. LCS란 공통 문자열 중 길이가 가장 긴 문자열을 말한다. 이 때 공통 문자열을 이루는 문자들 사이에 다른 문자열이 있어도 상관없으며 공통 문자열을 이루는 문자들의 순서만 동일하면 된다. LCS가 길수록 두 문자열이 유사도가 높다고 할 수 있다. 이 LCS의 길이와 LCS를 구하는 알고리즘이 LCS 알고리즘이며, 이를 직접 코드로 구현해보고자 한다. 

2. LCS 알고리즘 구현 코드 (python)

입력: 첫번째 줄에 문자열 X를 입력하고 두번째 줄에 문자열 Y를 입력한다. (문자열을 입력할 때는 문자와 문자 사이에 공백을 두고 입력한다.)
출력: 첫번째 줄에 LCS의 길이를 출력하고 두번째 줄에 그 LCS 중 하나를 출력한다. 

import sys
input = sys.stdin.readline

def LCSlength(x, y, m, n):
    b = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # 테이블 b 선언 및 초기화
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # 테이블 c 선언 및 초기화

    for i in range(1, m + 1): # i : 행을 나타내는 변수
        for j in range(1, n + 1): # j : 열을 나타내는 변수
            if x[i - 1] == y[j - 1]: # X의 i번째 문자와 Y의 j번째 문자가 같을 때
                c[i][j] = c[i - 1][j - 1] + 1 # 대각선의 값 + 1
                b[i][j] = '↖'
            else: # X의 i번째 문자와 Y의 j번째 문자가 같지 않을 때
                if c[i - 1][j] >= c[i][j - 1]: # 위쪽의 값이 더 클 경우
                    c[i][j] = c[i - 1][j] # 위쪽의 값을 그대로
                    b[i][j] = '↑'
                else: # 왼쪽의 값이 더 클 경우
                    c[i][j] = c[i][j - 1] # 왼쪽의 값을 그대로
                    b[i][j] = '←'

    return b, c

def printLCS(b, x, i, j):
    if i == 0 or j == 0: # 테이블의 끝에 도달하면 종료
        return
    if b[i][j] == '↖':
        printLCS(b, x, i - 1, j - 1) # 대각선 칸으로 이동
        print(x[i - 1], end = ' ') # 출력 (x[i - 1] == y[j - 1])
    elif b[i][j] == '↑':
        printLCS(b, x, i - 1, j) # 위쪽 칸으로 이동
    else:
        printLCS(b, x, i, j - 1) # 왼쪽 칸으로 이동

x = ''.join(input().split()) # 공백을 기준으로 나누어서 문자열로 저장
y = ''.join(input().split()) # 공백을 기준으로 나누어서 문자열로 저장
m = len(x) # m : X의 길이
n = len(y) # n : Y의 길이

b, c = LCSlength(x, y, m, n)

print("length of LCS :", c[m][n]) # length of longest common subsequence
print("LCS : ", end = '')
printLCS(b, x, m, n) # longest common subsequence

3. 출력 결과 화면

1) 입력: A B C B D A B
             B D C A B A
    출력: length of LCS : 4
             LCS : B C B A

 

2) 입력: 1 0 0 1 0 1 0 1
             0 1 0 1 1 0 1 1 0
    출력: length of LCS : 6
             LCS : 1 0 0 1 1 0

 

3) 입력: A C C G G T C G A G T
             G T C G T T C G G A A T
    출력: length of LCS : 7
             LCS : C G T C G A T