Longest Common Subsequence Screensaver
The Longest Common Subsequence screensaver fills a real dynamic-programming grid live, solving for the longest shared subsequence of two random strings and tracing it back. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Longest Common Subsequence screensaver works
The saver generates two real random strings and builds their longest-common-subsequence table cell by cell, live.
Each cell takes the real maximum of the cell above, the cell to the left, or a diagonal-plus-one whenever the two strings' characters match.
Once the grid is fully filled, the real optimal subsequence is traced back from the final cell to the origin, highlighting the path taken.
The traced subsequence holds briefly, then a fresh pair of random strings and a new grid fill begins.
Dynamic programming and the longest common subsequence
A subsequence keeps the order of the original characters but allows gaps, so it is more flexible than a substring. The longest common subsequence of two strings is the longest sequence that appears, in order, in both. The problem underlies the diff approach to comparing versions of text, and variations of it appear in comparing DNA and protein sequences.
Checking every possibility would be exponentially slow, but dynamic programming solves it in time proportional to the product of the two lengths. The idea is to solve smaller versions first and reuse them: each cell of the table stores the answer for a prefix of each string. If the two current characters match, the cell extends the diagonal neighbour by one. Otherwise it takes the better of the cell above and the cell to its left.
The final number in the corner is the length of the answer, but the sequence itself is recovered by walking back from that corner, following the choices that were made. When several routes tie, more than one valid subsequence of the same length can exist, so the path found is one of possibly several optimal answers. The related edit distance problem is solved with a very similar table.
A worked example
Wherever two strings share a matching character, the real grid cell jumps diagonally by one more than its upper-left neighbor, visibly building the longest shared subsequence step by step.
Settings & tips
- Accent recolours the cell currently being filled.
- This is a real, correct dynamic-programming LCS implementation.
- A fresh pair of strings generates automatically once the trace-back completes.
Frequently asked questions
- Is this a real dynamic-programming algorithm?
- Yes — a real, correct longest-common-subsequence table fill and trace-back, the same technique behind real diff tools.
- What does the highlighted path mean?
- It is the real, optimal longest subsequence shared by both strings, traced back through the filled grid.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- How is a subsequence different from a substring?
- A substring must be contiguous, while a subsequence only needs to keep the original order and may skip characters in between.
- Can there be more than one longest common subsequence?
- Yes. Ties in the table mean several different sequences can share the maximum length, and a traceback finds one of them.
- How does this relate to file comparison?
- Diff-style tools look for the longest sequence of lines common to both versions, and treat the remaining lines as added or removed.