Алгоритм Хиршберга

В предыдущих двух алгоритмах мы имели альтернативу: либо мы умеем восстанавливать ответ, либо можем себе позволить использовать $O(\min (m, n))$ дополнительной памяти. Алгоритм Хиршберга позволяет восстанавливать ответ, используя $O(\min (m, n)+$ $\log (\max (m, n)))$ дополнительной памяти. Идея алгоритма применима не только в этих двух, но и во многих других задачах.

Для определённости будем решать задачу о поиске НОП. В очередной раз применим метод “разделяй и властвуй”: отдельно решим задачу для последовательностей $a_{1}, \ldots, a_{n / 2}$ и $b_{1}, \ldots, b_{m}$, и для последовательностей $a_{n}, \ldots, a_{n / 2+1}$ и $b_{m}, \ldots, b_{1}$. И ту, и другую задачу решим, используя $O(m)$ дополнительной памяти.

Пусть в результате $l[j]$ - длина НОП $a_{1}, \ldots, a_{n / 2}$ и $b_{1}, \ldots, b_{j} ; r[j]$ - длина НОП $a_{n}, \ldots, a_{n / 2+1}$ и $b_{m}, \ldots, b_{m+1-j}$. Тогда длина НОП $a_{1}, \ldots, a_{n}$ и $b_{1}, \ldots, b_{m}$ - это максимум $l[j]+r[m-j]$ по $0 \leqslant j \leqslant m$.

Пусть максимальное значение достигается на $j_{\max }$. Сделаем рекурсивные запуски алгоритма от $a_{1}, \ldots, a_{n / 2}$ и $b_{1}, \ldots, b_{j_{\max }}$ и от $a_{n / 2+1}, \ldots, a_{n}$ и $b_{j_{\max }+1}, \ldots, b_{m}$, чтобы восстановить половинки ответа.

Глубина рекурсии составит $O(\log n)$, каждый рекурсивный запуск может переиспользовать одни и те же $O(m)$ дополнительной памяти, значит, всего понадобится $O(m+\log n)$ дополнительной памяти.

Осталось понять, почему оценка времени работы по-прежнему равна $O(m n)$. Посмотрим на все рекурсивные вызовы на глубине $k$. Во всех них первая последовательность имеет длину $O\left(n / 2^{k}\right)$, а сумма длин вторых последовательностей по всем вызовам на глубине $k$ равна $m$. Значит, суммарное время работы рекурсивных вызовов на глубине $k$ равно $O\left(m n / 2^{k}\right)$. Тогда суммарное время работы всех вызовов есть

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

hirschberg(a, b):
    n = len(a), m = len(b)
    if n <= 1 or m <= 1:
        # если одна из последовательностей имеет длину не больше 1,
        # решим задачу обычным алгоритмом
        return naiveLCS(a, b)
    l= getLCS (a[0, n / 2), b)
    r = getLCS(reverse(a[n / 2, n)), reverse(b))
    j = argmax (l[j] + r[m - j], j = 0..m)
    return hirschberg(a[0, n / 2), b[0, j))
            + hirschberg(a[n / 2, n), b[j, m))

Альтернативный способ

Другой способ, работающий по тем же причинам: будем действовать, как обычно при восстановлении ответа, но запоминать будем не предыдущее состояние, а состояние на оптимальном пути от начального с $i=n / 2$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int l[2][m + 1]
int mid[2][m + 1]
relax(i, j, newL, newMid):
    if l[i, j] < newL:
        l[i, j] = newL, mid[i, j] = newMid
hirschberg(a, b):
    n = len(a), m = len(b)
    if n <= 1 or m <= 1:
        return naiveLCS(a, b)
    fill(l, 0), fill(mid, 0)
    for i = 1..n:
        cur = i % 2, prev = 1 - cur
        for j = 1..m:
            relax(cur, j, l[prev, j], mid[prev, j])
            relax(cur, j, l[cur, j - 1], mid[cur, j - 1])
            if a[i] == b[j]:
                relax(cur, j, l[prev, j - 1] + 1, mid[prev, j - 1])
            if i == n / 2:
                mid[cur, j] = j
    j = mid[n, m]
    return hirschberg(a[0, n / 2), b[0, j))
            + hirschberg(a[n / 2, n), b[j, m))