 It can be solved in polynomial time by dynamic programming; this basic algorithm has additional speedups for small alphabets (the Method of Four Russians), for strings with few differences, for strings with few matching pairs of characters, etc.This problem and its generalizations to more complex forms of edit distance have important applications in areas that include bioinformatics (in the comparison of DNA and protein sequences and the reconstruction of evolutionary trees), geology (in stratigraphy), and computer science (in data comparison and revision control).One motivation for studying the longest common subsequences of random strings, given already by Chvátal and Sankoff, is to calibrate the computations of longest common subsequences on strings that are not random.