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:
“Light is meaningful only in relation to darkness, and truth presupposes error. It is these mingled opposites which people our life, which make it pungent, intoxicating. We only exist in terms of this conflict, in the zone where black and white clash.”
—Louis Aragon (1897–1982)
“Light is meaningful only in relation to darkness, and truth presupposes error. It is these mingled opposites which people our life, which make it pungent, intoxicating. We only exist in terms of this conflict, in the zone where black and white clash.”
—Louis Aragon (1897–1982)
“I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.”
—Alice Foote MacDougall (1867–1945)