# Number of optimal solutions for Longest Common Subsequence (Substring) problem

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\}$.
$$s_1 = a^n, s_2 = a^{2n}$$
The longest common subsequence has length $$n$$. There are [$$2n$$ choose $$n$$] such longest subsequences, or $$\frac{(2n)!}{n!n!} = \frac{2n \cdot \ldots \cdot (n+1)}{n \cdot \ldots \cdot 1} = \frac{2n}{n} \cdot (\ldots )\cdot \frac{n+1}{1}$$. Each factor in this product is at least 2 and there are $$n$$ factors, so this is at least $$2^n$$.