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\}$.