LCS

LCS의 길이 구하기

 

두 문자열 A, B 가 있다고 하자.

 

$X_i$ = A[0]...A[i]

$Y_j$ = B[0]...B[j]

로 정의하자.

 

d[i][j] 를 LCS($X_i$, $Y_j$)의 길이라고 하자.

 

먼저 다음과 같은 사실이 자명하게 성립한다.

• d[i-1][j-1] $\leq$ d[i-1][j] $\leq$ d[i][j]
• d[i-1][j-1] $\leq$ d[i][j-1] $\leq$ d[i][j]
• d[i-1][j-1], d[i-1][j], d[i][j-1], d[i][j] 에서 어떤 둘을 골라도 그 차이는 1 이하이다.

 

 

1. a[i] == b[j] 일 때,

a[i] == b[j] 라는 사실과 별개로 d[i][j] = d[i-1][j-1] 혹은 d[i][j] = d[i-1][j-1] + 1 이 성립한다.

 

그런데 a[i] == b[j] 일 때, d[i][j] > d[i-1][j-1] 임이 확실하게 보장되므로

 

$\therefore$ d[i][j] = d[i-1][j-1] + 1

 

 

 

2. a[i] != b[j] 일 때,

LCS($X_i$, $Y_j$)는 절대로 A[i]와 B[j]를 동시에 포함할 수 없다.

 

따라서 LCS($X_i$, $Y_j$)는

 

LCS($X_{i-1}$, $Y_j$) 또는 LCS($X_i$, $Y_{j-1}$)과 같다.

 

이 때 둘의 크기가 다르다면 당연히 더 긴 것이 LCS($X_i$, $Y_j$)가 될 것이다.

 

$\therefore$ d[i][j] = max(d[i-1][j], d[i][j-1])

 

 

 

3. 물론 i = 0 or j = 0 일 때는 d[i][j-1] = d[i-1][j] = d[i-1][j-1] = 0 으로 계산하면 된다.

 

 

 

 

LCS 구하기

2차원 배열 fr을 만들어서 d[i][j] 를 기록할 때 d[i-1][j-1], d[i-1][j], d[i][j-1] 중 어느 값을 참조했는지 같이 기록해주면 된다. LCS에 새로운 항을 추가하는 건 A[i] == B[j] 조건이 포함될 때, 즉 대각선에 있는 d[i-1][j-1]의 값을 참조할 때이다. 

 

소스코드

a = " " + input().rstrip()
b = " " + input().rstrip()

n, m = len(a)-1, len(b)-1
d = [[0]*(m+1) for _ in range(n+1)] # a[i], b[j] 까지 고려했을 때 LCS의 길이
fr = [[0]*(m+1) for _ in range(n+1)] # d[i][j]를 뭘로부터 계산했는가 ( 1: 좌상단, 2 : 왼쪽, 3 : 위 )

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

            if d[i][j-1] > d[i][j]:
                d[i][j] = d[i][j-1]
                fr[i][j] = 2

print(d[n][m])

def func(x, y):
    if x == 0 or y == 0:
        return

    if fr[x][y] == 1:
        func(x-1, y-1)
        print(a[x], end="")
    elif fr[x][y] == 2:
        func(x, y-1)
    elif fr[x][y] == 3:
        func(x-1, y)

func(n, m)