1
$\begingroup$

I have done a coding exercise where the problem was to compute the maximal length of a common substring given two strings. Consider strings as finite sequences with elements in the English alphabet and substrings as subsequences in the usual way. For two strings $a=a_1\cdots a_m$ and $b=b_1\cdots b_n$ it seems that $m + n = l + s$ holds, here $l$ is the length of a longest common substring and $s$ is the length of the shortest string having both $a$ and $b$ as substrings. I can prove $s \leq m + n - l$ but can't work out the reverse inequlity to get the equality. Feels like I am missing some really simple counting argument ?

Edit: I should not have written "as usual". For the string $x = x_1\cdots x_k$ a substring is any $x_{i_1}\cdots x_{i_l}$ with $i_1 < \ldots and the empty string.

  • 0
    I don't see why this should be true (unless a substring doesn't have to appear contiguously). For example, if $a$ = "AB" and $b$ = "CBD" then $m = n = 2$, the length of the longest common substring (that is, "B") is 1, but the length of the shortest string having both $a$ and $b$ as substrings is $5$ (that would be "ABCBD" or "CBDAB")....2011-12-22
  • 0
    @sibilant: It’s clear that they *don’t* have to appear contiguously: that’s the point of ‘[c]onsider ... substrings as subsequences in the usual way’.2011-12-22
  • 0
    @Brian, but it is confusing because that is _not_ the "usual way" to use the word "substring".2011-12-22
  • 0
    @Henning: I agree, and I’d not use it that way myself, but it’s clearly what was intended.2011-12-22

1 Answers 1