LCS
acronymprogramming
Stands for: longest common subsequence
The longest sequence common to two inputs, keeping order.
The longest common subsequence is the basis of most diff tools: the longest ordered (but not necessarily contiguous) run of elements shared by two files. What is left over becomes the additions and deletions a diff shows.
The longest common subsequence is the longest sequence of elements appearing in the same order in two inputs, though not necessarily adjacently. It is the algorithm behind every diff you have ever read.
Understanding it explains why diffs sometimes look wrong. The algorithm finds a minimal edit script, not the change a human made, so moving a block of code appears as a deletion and an insertion, and a small edit inside a repetitive region can align against the wrong instance and produce a confusing hunk. Modern tools add heuristics for exactly this reason, and knowing the underlying algorithm is what makes an odd diff explicable rather than mysterious.
Also known as: lcs