created, $=dv.current().file.ctime & modified, =this.modified
tags:nlpcs
Longest subsequence common to all sequence in a set of sequences (often just two sequences). Unlike substring commonality, the subsequences are not required to occupy consecutive positions.
s1 = ABC s2 = ACBAD
2 length CS = AB, AC, AD, BD, CD 3 length CS = ABD ACD
So ABD, ACD are longest common subsequences.
LCS on random strings
Beginning with Chvátal & Sankoff (1975),a number of researchers have investigated the behavior of the longest common subsequence length when the two given strings are drawn randomly from the same alphabet. When the alphabet size is constant, the expected length of the LCS is proportional to the length of the two strings, and the constants of proportionality (depending on alphabet size) are known as the Chvátal–Sankoff constants. Their exact values are not known, but upper and lower bounds on their values have been proven, and it is known that they grow inversely proportionally to the square root of the alphabet size. Simplified mathematical models of the longest common subsequence problem have been shown to be controlled by the Tracy–Widom distribution.