최장 공통 부분 수열

두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)은 두 문자열에 동일한 순서로 나타나는 가장 긴 문자 시퀀스를 의미한다.

예를 들어, "Hello World"와 "Bonjour le monde"의 LCS는 "oorld"이다. 두 문자열을 왼쪽에서 오른쪽으로 순서대로 살펴보면, o, o, r, l, d가 동일한 순서로 나타난다는 것을 확인할 수 있다.

다른 가능한 부분 수열로는 "ed"와 "old"가 있지만, 이들은 모두 "oorld"보다 짧다.

참고: 이 개념은 최장 공통 부분 문자열(Longest Common Substring) 문제와 혼동하면 안 된다. 부분 문자열의 경우 문자들이 반드시 인접해야 하지만, 부분 수열에서는 문자가 서로 떨어져 있어도 상관없다. 단지 같은 순서로 나타나기만 하면 된다.

두 문자열 a와 b의 LCS를 찾는 한 가지 방법은 동적 프로그래밍과 백트래킹 전략을 사용하는 것이다.

동적 프로그래밍으로 LCS 길이 찾기

먼저, 문자열 a와 b 사이의 가장 긴 공통 부분 수열(LCS)의 길이를 찾는다. 아직 실제 부분 수열을 찾는 것은 아니고, 길이만을 구한다.

a와 b의 모든 부분 문자열 조합에 대한 LCS의 길이를 구하기 위해 동적 프로그래밍 기법을 사용한다. 동적 프로그래밍은 모든 가능성을 계산하고 이를 룩업 테이블에 저장하는 방식이다.

참고: 다음 설명에서 n은 문자열 a의 길이이고, m은 문자열 b의 길이이다.

모든 가능한 부분 수열의 길이를 찾기 위해 헬퍼 함수 lcsLength(_:)를 사용한다. 이 함수는 크기가 (n+1) x (m+1)인 행렬을 생성한다. 여기서 matrix[x][y]는 부분 문자열 a[0...x-1]과 b[0...y-1] 사이의 LCS 길이를 나타낸다.

예를 들어, 문자열 "ABCBX"와 "ABDCAB"가 주어졌을 때, lcsLength(_:)의 출력 행렬은 다음과 같다:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |  
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| B | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| X | 0 | 1 | 2 | 2 | 3 | 3 | 4 |

이 예에서 matrix[3][4]의 값은 3이다. 이는 a[0...2]와 b[0...3], 즉 "ABC"와 "ABDC" 사이의 LCS 길이가 3임을 의미한다. 이는 두 부분 문자열이 ABC라는 공통 부분 수열을 가지고 있기 때문에 맞는 결과이다. (참고: 행렬의 첫 번째 행과 열은 항상 0으로 채워진다.)

lcsLength(_:)의 소스 코드는 다음과 같다. 이 코드는 String의 확장에 포함된다:

func lcsLength(_ other: String) -> [[Int]] {

  var matrix = [[Int]](repeating: [Int](repeating: 0, count: other.characters.count+1), count: self.characters.count+1)

  for (i, selfChar) in self.characters.enumerated() {
	for (j, otherChar) in other.characters.enumerated() {
	  if otherChar == selfChar {
		// 공통 문자를 찾았으므로, 지금까지 찾은 가장 긴 LCS 길이에 1을 더한다.
		matrix[i+1][j+1] = matrix[i][j] + 1
	  } else {
		// 일치하지 않으면, 지금까지 찾은 가장 긴 LCS 길이를 전파한다.
		matrix[i+1][j+1] = max(matrix[i][j+1], matrix[i+1][j])
	  }
	}
  }

  return matrix
}

먼저, 이 함수는 새로운 행렬(실제로는 2차원 배열)을 생성하고 0으로 채운다. 그런 다음, 문자열 self와 other을 순회하며 각 문자를 비교하여 행렬을 채운다. 두 문자가 일치하면 부분 수열의 길이를 1 증가시킨다. 그러나 두 문자가 다르면 지금까지 찾은 가장 긴 LCS 길이를 전파한다.

다음과 같은 상황을 가정해 보자:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |  
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | * |   |   |   |
| B | 0 |   |   |   |   |   |   |
| X | 0 |   |   |   |   |   |   |

*는 현재 비교하고 있는 두 문자 C와 D를 나타낸다. 이 두 문자는 일치하지 않으므로, 지금까지 찾은 가장 긴 길이인 2를 전파한다:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |  
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | * |   |   |
| B | 0 |   |   |   |   |   |   |
| X | 0 |   |   |   |   |   |   |

이제 C와 C를 비교한다. 이 두 문자는 일치하므로 길이를 3으로 증가시킨다:

|   | Ø | A | B | D | C | A | B |
| Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 | 1 | 1 |  
| B | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| C | 0 | 1 | 2 | 2 | 3 | * |   |
| B | 0 |   |   |   |   |   |   |
| X | 0 |   |   |   |   |   |   |

이런 방식으로 lcsLength(_:)는 전체 행렬을 채워 나간다.

실제 부분 수열을 찾기 위한 역추적

지금까지 모든 가능한 부분 수열의 길이를 계산했다. 가장 긴 부분 수열의 길이는 행렬의 오른쪽 하단인 matrix[n+1][m+1]에서 찾을 수 있다. 위 예제에서는 4이므로 LCS는 4개의 문자로 구성된다.

모든 부분 문자열 조합의 길이를 알면 역추적 전략을 사용해 LCS를 구성하는 문자를 찾을 수 있다.

역추적은 matrix[n+1][m+1]에서 시작하며, 위와 왼쪽(이 우선순위로)으로 이동하며 단순 전파가 아닌 변화를 찾는다.

|   |  Ø|  A|  B|  D|  C|  A|  B|
| Ø |  0|  0|  0|  0|  0|  0|  0|
| A |  0|↖ 1|  1|  1|  1|  1|  1|  
| B |  0|  1|↖ 2|← 2|  2|  2|  2|
| C |  0|  1|  2|  2|↖ 3|← 3|  3|
| B |  0|  1|  2|  2|  3|  3|↖ 4|
| X |  0|  1|  2|  2|  3|  3|↑ 4|

각 ↖ 이동은 LCS에 속하는 문자(행/열 헤더에 있는)를 나타낸다.

왼쪽과 위쪽의 숫자가 현재 셀의 숫자와 다르면 전파가 발생하지 않았다는 뜻이다. 이 경우 matrix[i][j]는 문자열 a와 b 사이의 공통 문자를 나타내므로, a[i - 1]과 b[j - 1]에 있는 문자가 우리가 찾는 LCS의 일부다.

한 가지 주의할 점은 역추적이 실행되면서 LCS가 역순으로 생성된다는 것이다. 반환하기 전에 결과를 뒤집어 실제 LCS를 반영한다.

다음은 역추적 코드다:

func backtrack(_ matrix: [[Int]]) -> String {
  var i = self.characters.count
  var j = other.characters.count
  
  var charInSequence = self.endIndex
  
  var lcs = String()
  
  while i >= 1 && j >= 1 {
	// 전파가 변경 없이 발생한 경우: LCS에 새 문자가 추가되지 않았다.
	if matrix[i][j] == matrix[i][j - 1] {
	  j -= 1
	}
	// 전파가 변경 없이 발생한 경우: LCS에 새 문자가 추가되지 않았다.
	else if matrix[i][j] == matrix[i - 1][j] {
	  i -= 1
	  charInSequence = self.index(before: charInSequence)
	}
	// 왼쪽과 위쪽의 값이 현재 셀과 다르다.
	// 이는 LCS 길이에 1이 추가되었음을 의미한다.
	else {
	  i -= 1
	  j -= 1
	  charInSequence = self.index(before: charInSequence)
	  lcs.append(self[charInSequence])
	}
  }
  
  return String(lcs.characters.reversed())
}

이 코드는 matrix[n+1][m+1](오른쪽 하단)에서 matrix[1][1](왼쪽 상단)으로 역추적하며 두 문자열에 공통된 문자를 찾는다. 이 문자를 새로운 문자열 lcs에 추가한다.

charInSequence 변수는 self로 주어진 문자열의 인덱스다. 초기에는 문자열의 마지막 문자를 가리킨다. i를 감소시킬 때마다 charInSequence도 뒤로 이동한다. 두 문자가 같다고 판단되면 self[charInSequence]에 있는 문자를 새로운 lcs 문자열에 추가한다. (self[i]를 바로 쓸 수 없는 이유는 i가 Swift 문자열 내의 현재 위치와 매핑되지 않을 수 있기 때문이다.)

역추적 때문에 문자가 역순으로 추가되므로, 함수 마지막에 reversed()를 호출해 문자열을 올바른 순서로 만든다. (문자열 끝에 새 문자를 추가한 후 한 번 뒤집는 것이 항상 문자열 앞에 문자를 삽입하는 것보다 빠르다.)

전체 과정 정리

두 문자열 간의 최장 공통 부분 수열(LCS)을 찾기 위해 먼저 lcsLength(_:)를 호출한 다음 backtrack(_:)을 호출한다:

extension String {
  public func longestCommonSubsequence(_ other: String) -> String {

    func lcsLength(_ other: String) -> [[Int]] {
      ...
    }
    
    func backtrack(_ matrix: [[Int]]) -> String {
      ...
    }

    return backtrack(lcsLength(other))
  }
}

모든 것을 깔끔하게 정리하기 위해 두 헬퍼 함수를 메인 longestCommonSubsequence() 함수 내부에 중첩했다.

다음은 Playground에서 이를 시도해 볼 수 있는 방법이다:

let a = "ABCBX"
let b = "ABDCAB"
a.longestCommonSubsequence(b)   // "ABCB"

let c = "KLMK"
a.longestCommonSubsequence(c)   // "" (공통 부분 수열 없음)

"Hello World".longestCommonSubsequence("Bonjour le monde")   // "oorld"

Swift Algorithm Club을 위해 Pedro Vereza가 작성