The Longest Common Subsequence (or Substring) problem (LCS) asks, given two strings $s_1$ and $s_2$, to find one string which is substring both of $s_1$ and $s_2$ and it is of maximum length.

Each instance of the problem (i.e. each choice of $s_1$ and $s_2$) can have multiple optimal solutions. The size input of the problem is the sum of the length of $s_1$ and $s_2$.

Is the number of optimal solutions polynomial with respect to the size of the instance?


Consider the following two strings: $$ s_1 = (abc)^n, s_2 = (bac)^n. $$ You can show that the longest common substrings of $s_1,s_2$ have length $2n$. There are at least $2^n$ of these: $\sigma_1 c \sigma_2 c \ldots \sigma_n c$, where $\sigma_i \in \{a,b\}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.