문자열 3개의 가장 긴 공통 부분문자열(Longest Common Subsequence)구하기

1. 문제

 

1958번: LCS 3 (acmicpc.net)

1958번: LCS 3

 

2. 풀이

 

문자열 X[1,2,...,i]와 Y[1,2,..,j]와 Z[1,2,..,k]의 가장 긴 공통부분문자열을 dp[i][j][k]라고 하자.

 

그러면 2개의 문자열 LCS를 구할때와 동일한 방법으로 DP배열을 채울 수 있다

 

https://deepdata.tistory.com/1022

LCS(Longest Common Subsequence) 문제 다이나믹 프로그래밍 기본 해법 배우기

 

문자 $x_{i}$와 $y_{j}$와 $z_{k}$가 모두 같을 때, 나머지 X[1,2,..,i-1], Y[1,2,..,j-1], Z[1,2,..,k-1]의 가장 긴 공통 부분문자열의 길이 dp[i-1][j-1][k-1]에 1을 더하면 된다

 

하지만 어느 하나라도 다르다면... X[1,2,...,i-1], Y[1,2,..,j], Z[1,2,...,k]의 가장 긴 공통 부분문자열 길이 dp[i-1][j][k]

 

X[1,2,..,i], Y[1,2,..,j-1], Z[1,2,..,k]의 가장 긴 공통 부분문자열 길이 dp[i][j-1][k]

 

X[1,2,..,i], Y[1,2,..,j], Z[1,2,..,k-1]의 가장 긴 공통 부분문자열 길이 dp[i][j][k-1]중 최댓값이 된다

 

이렇게 모든 i = 1,2,..,len(X), j = 1,2,..,len(Y), k = 1,2,..,len(Z)에 대해 순회하면 dp[len(X)][len(Y)][len(Z)]에 LCS 길이가 있다

 

#3개 문자열 X,Y,Z의 LCS 구하기
X = input()
Y = input()
Z = input()

n = len(X)
m = len(Y)
l = len(Z)

#문자열 X[1,2,...,i]와 Y[1,2,..,j]와 Z[1,2,..,k]의 가장 긴 공통부분문자열의 길이 dp[i][j][k]
dp = [[[0]*(l+1) for _ in range(m+1)] for _ in range(n+1)]

#X[i], Y[j], Z[k]가 모두 같을때, dp[i][j][k]는 dp[i-1][j-1][k-1]에 1을 더해준것
#그렇지 않으면, 각각 하나 뺀 dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]중 최댓값
for i in range(1,n+1):
    
    for j in range(1,m+1):
        
        for k in range(1,l+1):
            
            if X[i-1] == Y[j-1] and Y[j-1] == Z[k-1]:
                
                dp[i][j][k] = dp[i-1][j-1][k-1] + 1
            
            else:
                
                dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

#모두 순회해서 dp배열을 채우면, dp[n][m][l]에 LCS의 길이가 있다
print(dp[n][m][l])

 

여기서 이런 생각을 할 수도 있는데..

 

두 문자열 X,Y에 대해 실제 LCS로 W를 구한 다음, W와 다른 문자열 Z에 대해 LCS의 길이를 구한다면?

 

근데 이렇게 하면 두 문자열 X,Y의 LCS는 여러개 있을 수 있는데... 실제 LCS는 아무거나 하나만 구해지므로,

 

그렇게 구한 LCS W와 Z의 LCS가 X,Y,Z 3개 문자열의 LCS가 된다는 보장이 없다...

 

def lcs(X,Y):
    
    n = len(X)
    m = len(Y)

    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(1,n+1):
        
        for j in range(1,m+1):
            
            if X[i-1] == Y[j-1]:
                
                dp[i][j] = dp[i-1][j-1] + 1
            
            else:
                
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    
    return dp

def get_lcs(dp,n,m,X):
    
    i = n
    j = m

    lcs = [0]*(dp[i][j])

    k = 1

    while i != 0 or j != 0:
        
        if j >= 1 and dp[i][j] == dp[i][j-1]:
            
            j -= 1
        
        elif dp[i][j] == dp[i-1][j]:
            
            i -= 1
        
        else:
            
            lcs[-k] = X[i-1]
            i -= 1
            j -= 1
            k += 1
    
    return ''.join(lcs)

s1 = input()
s2 = input()
s3 = input()

dp = lcs(s1,s2)
s4 = get_lcs(dp,len(s1),len(s2),s1)

dp = lcs(s3,s4)

print(dp[len(s3)][len(s4)])