Longest common subsequence by dynamic programming
For string suffixes A[i:],B[j:], let L(i,j) be their longest common subsequence length.
Key knowledge
For string suffixes A[i:],B[j:], let L(i,j) be their longest common subsequence length. Empty suffixes give zero; matching first characters give 1+L(i+1,j+1), otherwise max(L(i+1,j),L(i,j+1)). Filling indices backwards solves the problem in O((m+1)(n+1)) time and table space; predecessor choices recover a subsequence.
Conditions and scope
- m,n are string lengths; symbol equality has unit cost.
- A subsequence need not be contiguous; this is different from longest common substring.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture16 LCS subproblem, recurrence, order, base cases, reconstruction and complexity, printed2–3.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-longest-common-subsequence
- Revision
- university-core.1
- Structured reference record
- University core expansion