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.
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.
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.