Hirschberg (히르쉬버그) LCS

정의

Hirschberg 알고리즘 은 두 문자열 A, B 의 LCS 를 O(N) 공간 (메모리) 만 사용해 구하는 분할 정복 DP. 표준 LCS 의 O(NM) 공간을 O(N) 으로 줄이면서도 시간은 O(NM) 유지.

1975 년 D. S. Hirschberg 가 제안. 아이디어: LCS 를 반으로 나누고, 중간 지점에서 분할점을 찾아 재귀.

문제 상황과 동기

표준 LCS 는 O(NM) 공간. N = M = 10^5 면 10^10 int = 40 GB. 메모리 초과.

• naive DP: dp[N+1][M+1] 전체 저장. 수열 복원 가능. 공간 O(NM).
• 공간 최적화 (1 행): prev, curr 만 유지. 길이는 알 수 있지만 traceback 불가.
• Hirschberg: O(NM) 시간, O(N) 공간, traceback 으로 수열 복원까지 가능.

핵심 통찰: LCS DP 는 재귀적으로 분할 가능. “A 의 왼쪽 절반과 B 전체” 의 LCS + “A 의 오른쪽 절반과 B 전체” 의 LCS = 전체 LCS. 분할점을 찾아 재귀.

시각화

핵심 아이디어

분할 정복 LCS

lcs(A, B) 의 해를 A 의 중간 mid = N/2 에서 분할:

LCS(A, B) = LCS(A[0..mid], B[..k]) + LCS(A[mid..], B[k..])

k 는 다음 조건을 만족하는 위치:

fwd[mid][k] + rev[N-mid][M-k] = LCS(A, B)

여기서 fwd[i][j] = A[0..i-1], B[0..j-1] 의 LCS 길이. rev[i][j] = A[N-i..N-1], B[M-j..M-1] 의 LCS 길이 (뒤에서부터).

분할점 k 찾기

1. fwd[mid] 행 (A 의 중간까지, B 전체와의 LCS 길이) 을 O(NM) DP 로 계산. 단, O(M) 공간만 사용 (1 행).
2. rev[N-mid] 행 (A 의 나머지 절반, B 전체와의 LCS 길이) 을 O(NM) DP 로 계산. (뒤에서부터)
3. fwd[mid][k] + rev[N-mid][M-k] 가 최대가 되는 k = 분할점.
4. 왼쪽 lcs(A[0..mid], B[0..k]) + 오른쪽 lcs(A[mid..], B[k..]) 재귀.

기저 조건

N = 0 또는 M = 0: 빈 문자열. N = 1: 단일 문자 LCS (선형 탐색, O(M)).

알고리즘

hirschberg(A, B):
    N = len(A), M = len(B)

    if N == 0 or M == 0: return ""
    if N == 1:
        if A[0] in B: return A[0]
        else: return ""

    mid = N // 2
    fwd = lcs_row(A[0..mid], B)     // O(mid * M) 공간 O(M)
    rev = lcs_row_rev(A[mid..], B)  // O((N-mid) * M) 공간 O(M)

    // 분할점 k
    best = -1; k = 0
    for j in 0..M:
        total = fwd[j] + rev[M - j]
        if total > best: best = total; k = j

    return hirschberg(A[0..mid], B[0..k])
         + hirschberg(A[mid..], B[k..])

lcs_row 함수:

lcs_row(A, B):
    prev = [0] * (M + 1)
    for i in 1..len(A):
        curr = [0] * (M + 1)
        for j in 1..M:
            if A[i-1] == B[j-1]: curr[j] = prev[j-1] + 1
            else: curr[j] = max(prev[j], curr[j-1])
        prev = curr
    return prev

구현

// Hirschberg LCS - O(NM) time, O(N) space
#include <bits/stdc++.h>
using namespace std;
​
vector<int> lcs_row(const string& a, const string& b) {
  int m = b.size();
  vector<int> prev(m + 1, 0), curr(m + 1, 0);
  for (char ca : a) {
      for (int j = 1; j <= m; j++) {
          if (ca == b[j-1])
              curr[j] = prev[j-1] + 1;
          else
              curr[j] = max(prev[j], curr[j-1]);
      }
      swap(prev, curr);
  }
  return prev;
}
​
string hirschberg(const string& a, const string& b) {
  int n = a.size(), m = b.size();
  if (n == 0) return "";
  if (n == 1) {
      return (b.find(a[0]) != string::npos) ? string(1, a[0]) : "";
  }
​
  int mid = n / 2;
  auto fwd = lcs_row(a.substr(0, mid), b);
  string ra = a.substr(mid);
  reverse(ra.begin(), ra.end());
  string rb = b;
  reverse(rb.begin(), rb.end());
  auto rev = lcs_row(ra, rb);
​
  int best = -1, k = 0;
  for (int j = 0; j <= m; j++) {
      int total = fwd[j] + rev[m - j];
      if (total > best) { best = total; k = j; }
  }
​
  return hirschberg(a.substr(0, mid), b.substr(0, k))
       + hirschberg(a.substr(mid), b.substr(k));
}
​
int main() {
  string a, b;
  cin >> a >> b;
  string ans = hirschberg(a, b);
  cout << ans.size() << "\n" << ans << "\n";
}

# Hirschberg LCS - O(NM) time, O(N) space
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
​
def lcs_row(a: str, b: str):
  m = len(b)
  prev = [0] * (m + 1)
  for ca in a:
      curr = [0] * (m + 1)
      for j in range(1, m + 1):
          if ca == b[j-1]:
              curr[j] = prev[j-1] + 1
          else:
              curr[j] = prev[j] if prev[j] > curr[j-1] else curr[j-1]
      prev = curr
  return prev
​
def hirschberg(a: str, b: str) -> str:
  n, m = len(a), len(b)
  if n == 0:
      return ""
  if n == 1:
      return a[0] if a[0] in b else ""
​
  mid = n // 2
  fwd = lcs_row(a[:mid], b)
  rev = lcs_row(a[mid:][::-1], b[::-1])
​
  best, k = -1, 0
  for j in range(m + 1):
      total = fwd[j] + rev[m - j]
      if total > best:
          best, k = total, j
​
  return (hirschberg(a[:mid], b[:k])
        + hirschberg(a[mid:], b[k:]))
​
a = input().strip()
b = input().strip()
ans = hirschberg(a, b)
print(len(ans))
print(ans)

ABCBDAB
BDCAB

4
BCAB

ABCD
EFGH

0

A
B

0

복잡도

표준 LCS 와 같은 시간 복잡도지만 공간이 O(NM) -> O(N). N=10^5, M=10^5 일 때 메모리 40 GB -> 400 KB.

공간 분석

• 각 재귀 단계에서 O(M) 배열만 유지. 분할 정복으로 스택 깊이 O(log N).
• 전체 공간 O(M). traceback 에 추가 배열 불필요.

변형 / 활용

Hirschberg + Bitset LCS

Bitset LCS (O(NM/64)) 의 lcs_row 로 대체해 시간도 가속. 공간 O(N) + 시간 O(NM/64).

병렬화

분할 후 왼쪽/오른쪽 재귀가 독립적. 병렬 실행 가능.

Needleman-Wunsch (생물정보학)

전체 서열 정렬 (global alignment) 에 Hirschberg 기법 적용. 메모리 제한이 큰 게놈 정렬에 필수.

함정

1. 재귀 깊이

N 이 10^5 이면 재귀 깊이 log N ~ 17. Python 은 recursionlimit 확인.

2. 분할점 k 의 유일성

여러 k 가 같은 total 을 만들 수 있음. 아무 k 나 선택해도 LCS 결과는 동일 (최적 중 하나).

3. reverse 연산

뒤에서부터 DP (rev) 를 위해 문자열 reverse. 인덱스 매핑 실수 주의. rev[m - j] 가 올바른 매칭.

4. N = 1 기저 조건

문자 하나짜리 부분 문자열은 선형 탐색. 모든 재귀 단계에서 이 보호 없으면 무한 재귀.

BOJ 연습 문제

참고

• 최장 공통 부분 수열 (LCS)
• 비트셋 LCS (Hyyro)
• 동적 계획법
• D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences (1975)