183
Longest common substring
Here’s
the grid for
hish vs. vista.
One thing to note: for this problem, the final solution may not be in
the last cell!
For the knapsack problem, this last cell always had the
final solution. But for the longest common substring,
the solution is the
largest number in the grid—and it may not be the last cell.
Let’s go back to the original question: which string has more in
common with
hish? hish
and
fish
have a substring of three letters in
common.
hish
and
vista
have a substring of two letters in common.
Alex
probably meant to type
fish
.
Longest common subsequence
Suppose Alex accidentally searched for
fosh
. Which word did he mean:
fish
or
fort
?
Let’s compare them using the longest-common-substring formula.
184
Chapter 9
I
Dynamic programming
They’re both the same: two letters! But
fosh
is
closer to
fish
.
You’re comparing the longest common
substring
, but you really need
to
compare the longest common
subsequence
: the number of letters in
a sequence that the two words have in common. How do you calculate
the longest common subsequence?
Here’s
the partial grid for
fish
and
fosh
.
Can you figure out the formula for this grid? The longest common
subsequence is very similar to the longest common substring, and
the
formulas are pretty similar, too. Try to solve it yourself—I give the
answer next.
Dostları ilə paylaş: