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:
“We must get back into relation, vivid and nourishing relation to the cosmos and the universe. The way is through daily ritual, and is an affair of the individual and the household, a ritual of dawn and noon and sunset, the ritual of the kindling fire and pouring water, the ritual of the first breath, and the last.”
—D.H. (David Herbert)
“A theory of the middle class: that it is not to be determined by its financial situation but rather by its relation to government. That is, one could shade down from an actual ruling or governing class to a class hopelessly out of relation to government, thinking of gov’t as beyond its control, of itself as wholly controlled by gov’t. Somewhere in between and in gradations is the group that has the sense that gov’t exists for it, and shapes its consciousness accordingly.”
—Lionel Trilling (1905–1975)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)