LCS 알고리즘

[ LCS 정의 ]

 

LCS는 Longest Common Substring, Longest Common Subsequence 두 가지를 의미합니다.

 

Longest Common Substring는 최장 공통 문자열,

Longest Common Subsequence는 최장 공통 부분수열.

 

[ 둘의 차이점은? ]

 

둘의 차이점은 연결되는 문자열인가, 수열인가의 차이입니다.

 

최장 공통 부분수열은 수열을 찾는것이기 때문에 연결되지 않아도 문제없습니다.

 

ABCDEF

GBCDFE

-> BCDF

 

ABCDEF

GBCDFE

-> BCDE

 

하지만 최장 공통 문자열은 문자열이기 때문에 연결되어 있는 동시에 공통된 문자열을 찾아야 합니다.

 

ABCDEF

GBCDFE

-> BCD

 

---

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

 

구현 방법

 

LCS는 2차원 배열을 사용해 문자열1, 문자열2를 각각 행과 열에 매칭합니다. 구현 편의상 i, j가 0일 경우 0으로 할당하고 인덱스가 1인 경우부터 탐색합니다. 각각의 인덱스에 대하여 완전탐색을 실행합니다.

 

1. 2차원 배열 LCS를 선언하여

2. 문자열1 인덱스 i, 문자열2 인덱스 j를 하나씩 비교합니다.

3. 두 문자가 같다면 LCS[i][j] = LCS[ i - 1 ][ j - 1 ] + 1;

4. 두 문자가 다르다면 LCS[i][j] = 0;

5. 완전탐색이 종료되면 2차원 배열위의 가장 큰 숫자가 최장 공통 문자열의 길이

 

점화식

 

if (i == 0 || j == 0) {
    LCS[i][j] = 0;
} else if ( string1.charAt(i) == string2.charAt(j) ) {
    LCS[i][j] = LCS[i - 1][j - 1] + 1;
} else {
    LCS[i][j] = 0;
}

 

---

최장 공통 부분수열 ( Longest Common Subsequence)

 

구현 방법

 

기초적인 배열 선언, 탐색 방식은 최장 공통 문자열과 동일하나 두 문자가 다를때의 처리가 다릅니다.

 

1. 2차원 배열 LCS를 선언하여

2. 문자열1 인덱스 i, 문자열2 인덱스 j를 하나씩 비교합니다.

3. 두 문자가 같다면 LCS[i][j] = LCS[ i - 1 ][ j - 1 ] + 1;

4. 두 문자가 다르다면 LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);

5. 완전탐색이 종료되면 2차원 배열위의 가장 큰 숫자가 최장 공통 문자열의 길이

 

부분수열이기 때문에 문자열과 같이 이어지지 않아도 되므로 참조하는 두 문자가 다르다고 해서 0으로 초기화하지 않고 이전에 보았던 값중 더 큰 값을 기록해둡니다.

 

점화식

 

if (i == 0 || j == 0) {
    LCS[i][j] = 0;
} else if ( string1.charAt(i) == string2.charAt(j) ) {
    LCS[i][j] = LCS[i - 1][j - 1] + 1;
} else {
    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
}

 

 

최장 공통 부분수열 찾기

 

1. 결과값을 저장할 배열 result를 선언합니다.

2. LCS 2차원 배열의 마지막 원소에서 탐색을 시작.

3. LCS[i - 1][j] 와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾습니다.

4. 같은 값을 찾은 경우 해당 위치로 이동합니다.

5. 같은 값이 없다면 result 배열에 해당 위치의 문자를 result 배열에 넣고 LCS[i - 1][j - 1]로 이동합니다.

6. 모든 인덱스를 탐색합니다.

7. result에 저장된 문자를 역순으로 출력한 것이 LCS 입니다.