Longest Common Subsequence
Compare two texts and reconstruct a longest shared subsequence with a deterministic tie rule.
Free theory articleCompare two texts and reconstruct a longest shared subsequence with a deterministic tie rule.
Concept & interpretation
Compare two strings over the alphabet A, B, C, D and reconstruct their longest common subsequence (LCS) using prefix dynamic programming and deterministic ASCII-lexicographic tie breaking.
Experiment
Observe how the prefix dynamic programming table fills and breaks ties in https://riano.app/module/longest-common-subsequence:
- Enter First text
ABABand Second textBABA. - Click Step repeatedly to watch cells reveal in row-major order while final length and witness remain Pending.
- Click Finish to complete all 16 non-boundary cells and observe LCS length 3 with ASCII-smallest witness
ABA(chosen overBAB). - Clear First text to empty and verify that an empty string is immediately terminal with LCS length 0 and witness
Empty string.