[Algorithm] 최장 공통 문자열(Longest Common Subsequence)

최장 공통 문자열(Longest Common  Subsequence)

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
다이나믹 프로그래밍을 통해 해결한다.

 

 

 

 

ex) 백준 9252 LCS 2

 

https://www.acmicpc.net/problem/9252

ACAYKP
CAPCAK

를 입력받았을때 dp 배열

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 2, 2, 2]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 4]
[0, 1, 2, 3, 3, 3, 4]

import sys
from collections import deque
st1=[" "]
st2=[" "]
st1.extend(list(sys.stdin.readline().rstrip()))
st2.extend(list(sys.stdin.readline().rstrip()))


dp=[[0 for i in range(len(st2))] for i in range(len(st1))]
for i in range(1,len(st1)):
    for j in range(1,len(st2)):
        if(st1[i]==st2[j]):
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])
           
print(dp[-1][-1])

dq=deque()

y=len(st1)-1
x=len(st2)-1

while dp[y][x]!=0:
    if(dp[y][x]==dp[y][x-1]):
        x-=1
        continue
    elif(dp[y][x]==dp[y-1][x]):
        y-=1
        continue 
    else:
        dq.appendleft(st2[x])
        x-=1
        y-=1
print("".join(dq))