Comparing two sequences comes up in diff tools, spell checkers and DNA matching. LCS finds the longest sequence of characters common to both strings in the same order, using a table over prefixes of each string. Its pattern of match-and-extend or drop one character is the base for edit distance and many string DP problems. Do not confuse it with longest common substring, where the characters must be next to each other.