Relation To Other Problems
For two strings and, the length of the shortest common supersequence is related to the length of the LCS by
The edit distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion, is:
Read more about this topic: Longest Common Subsequence Problem
Famous quotes containing the words relation to, relation and/or problems:
“The difference between objective and subjective extension is one of relation to a context solely.”
—William James (1842–1910)
“The problem of the twentieth century is the problem of the color-line—the relation of the darker to the lighter races of men in Asia and Africa, in America and the islands of the sea. It was a phase of this problem that caused the Civil War.”
—W.E.B. (William Edward Burghardt)
“Belonging to a group can provide the child with a variety of resources that an individual friendship often cannot—a sense of collective participation, experience with organizational roles, and group support in the enterprise of growing up. Groups also pose for the child some of the most acute problems of social life—of inclusion and exclusion, conformity and independence.”
—Zick Rubin (20th century)