# Speeding Hirschberg Algorithm for Sequence Alignment

arXiv: https://arxiv.org/abs/2204.12801 · HTML: https://mlsanity.com/paper/2204.12801/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2022.

## Built on by (most cited first, 1 of 1)

- [Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch](https://mlsanity.com/paper/2608.08740/) (2026)

## Abstract (arXiv)

The use of Hirschberg algorithm reduces the spatial cost of recovering the Longest Common Subsequence to linear space. The same technique can be applied to similar problems like Sequence Alignment. However, the price to pay is a duplication of temporal cost. We present here a technique to reduce this time overhead to a negligible amount.