Hirschberg's algorithm in Python
Recovers an LCS in O(nm) time and O(n + m) space by divide and conquer on the middle row.
- File
hirschberg_lcs.py, 36 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hirschberg-lcs/. The authors are listed in prov/S3GJKS.jsonl.
from collections.abc import Sequence
from typing import TypeVar
T = TypeVar("T")
def lcs_row(x: Sequence[T], y: Sequence[T]) -> list[int]:
"""Return r with r[j] = length of an LCS of x and y[:j], in O(len(y)) space."""
r = [0] * (len(y) + 1) # @line L8
for xi in x: # @line L9
diag = 0 # @line L10
for j in range(1, len(y) + 1): # @line L11
up = r[j] # @line L12
if xi == y[j - 1]: # @line L13
r[j] = diag + 1
elif r[j - 1] > up:
r[j] = r[j - 1]
diag = up # @line L14
return r # @line L15
def hirschberg(x: Sequence[T], y: Sequence[T]) -> list[T]:
"""Return one longest common subsequence of x and y in O(len(x) + len(y)) space."""
m, n = len(x), len(y)
if m == 0 or n == 0: # @line L1
return []
if m == 1: # @line L2
return [x[0]] if x[0] in y else []
h = m // 2 # @line L3
f = lcs_row(x[:h], y) # @line L4
b = lcs_row(x[h:][::-1], y[::-1]) # @line L5
k = max(range(n + 1), key=lambda j: (f[j] + b[n - j], j)) # @line L6
return hirschberg(x[:h], y[:k]) + hirschberg(x[h:], y[k:]) # @line L7
test_hirschberg_lcs.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/hirschberg-lcs/. The authors are listed in prov/S3GJKS.jsonl.
import random
from hirschberg_lcs import hirschberg, lcs_row
def is_subsequence(z: list, x: list) -> bool:
it = iter(x)
return all(any(a == b for b in it) for a in z)
def table_lcs_length(x: str, y: str) -> int:
c = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
for i in range(1, len(x) + 1):
for j in range(1, len(y) + 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[len(x)][len(y)]
def test_example() -> None:
x, y = "ABCBDAB", "BDCABA"
assert lcs_row(x[:3], y) == [0, 1, 1, 2, 2, 2, 2]
assert lcs_row(x[3:][::-1], y[::-1]) == [0, 1, 2, 2, 2, 3, 4]
assert "".join(hirschberg(x, y)) == "BCBA"
def test_dna() -> None:
s1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"
s2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA"
assert "".join(hirschberg(s1, s2)) == "GTCGTCGGAAGCCGGCCGAA"
def test_edges() -> None:
assert hirschberg("", "") == []
assert hirschberg("A", "") == []
assert hirschberg("", "A") == []
assert hirschberg("A", "BAB") == ["A"]
assert hirschberg("ABC", "DEF") == []
assert hirschberg("ABCD", "ABCD") == list("ABCD")
assert hirschberg([1, 2, 3], [3, 2, 1]) in ([1], [2], [3])
def test_random_against_table() -> None:
rng = random.Random(1975)
for _ in range(500):
x = "".join(rng.choice("ABC") for _ in range(rng.randrange(14)))
y = "".join(rng.choice("ABC") for _ in range(rng.randrange(14)))
z = hirschberg(x, y)
assert len(z) == table_lcs_length(x, y) == lcs_row(x, y)[len(y)]
assert is_subsequence(z, list(x)) and is_subsequence(z, list(y))
What the next level needs
- the tests did not run in this build