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:
“Among the most valuable but least appreciated experiences parenthood can provide are the opportunities it offers for exploring, reliving, and resolving one’s own childhood problems in the context of one’s relation to one’s child.”
—Bruno Bettelheim (20th century)
“You see, I am alive, I am alive
I stand in good relation to the earth
I stand in good relation to the gods
I stand in good relation to all that is beautiful
I stand in good relation to the daughter of Tsen-tainte
You see, I am alive, I am alive”
—N. Scott Momaday (b. 1934)
“One of the annoying things about believing in free will and individual responsibility is the difficulty of finding somebody to blame your problems on. And when you do find somebody, it’s remarkable how often his picture turns up on your driver’s license.”
—P.J. (Patrick Jake)