A Fast Algorithm for Computing Longest Common Subsequences

Hunt, J. W., & Szymanski, T. G. (1977). A Fast Algorithm for Computing Longest Common Subsequences. Communications of the ACM, 350-353.

Type

Journal article

Intellectual base

Primary research

Year

1977

DOI

10.1145/359581.359603

Link

https://doi.org/10.1145/359581.359603

Cited by

1 citation across 1 artifact.

Domain-specific

• Hunt–Szymanski Algorithm
  • If \(r=|P|\) is much smaller than \(mn\), the work can be far below full dynamic programming; a standard bound is \(O((r+n)\log n)\) after appropriate preprocessing conventions, with reconstruction requiring predecessor records.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:cba4c98b8986 · see in the full table