LCS 최장 공통 부분 순서 구하기 (Python 코드)

Longest Common Subsequence

최장 공통 부분 순서

 

ex1)

bcdb는 abcbdab의 부분 순서이다.

- 연속되지 않아도 됨

 

ex2)

bca는 abcbdab와 bdcaba 두 문자열에 공통적으로 나타나는 부분 순서이다.

bcba는 두 문자열에 존재하는 최장 공통 부분 순서이다.

 

 

LCS의 길이를 구하는 알고리즘 

1. 재귀

int LCS(char *X, char *Y, m, n)
{
	if (m = 0 or n = 0) then return 0;
    else if (X[m - 1] = y[n - 1])then return LCS(X, Y, m - 1, n - 1) + 1;
    else return max(LCS(X, Y, m-1, n), LCS(X, Y, m, n-1)

}

재귀로 LCS를 구하면 엄청난 중복 호출이 발생한다

 

 

 

2. 동적계획법 Dynamic Programming

 

2차원 배열에 각 부분 문제의 답을 저장하면서 풀어나가는 방식

 

int lcs(int m, int n) //m, n은 각각 X, Y의 길이
{
	for (int i = 0; i <= m; i++)
    	c[i][0] = 0;
    for (int j = 0; j <= n; i++)
    	c[0][j] = 0;
    for (int i = 0; i <= m; i++)
    	for (int j = 0; j <= n; j++){
        	if (x[i] == y[j])
            	c[i][j] = c[i-1][j-1] + 1
            else
            	c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
        }
    }
    return c[m][n];
}

시간복잡도: Θ(mn)

(for문 총 mn번 반복)

 

 

 

파이썬으로 구현해본 LCS

X = input()
Y = input()

C= [[0] * (len(Y)+1) for _ in range(len(X) + 1)]

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

print(LCS(len(X), len(Y)))