# Number of different longest common substrings

Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common substrings of $w_1,w_2$. We can define $A(w_1,w_2)$ as follows: $$A(w_1,w_2)=\{s\in\Sigma^*\mid w_1=x_1sx_2,\;w_2=y_1sy_2,\;x_1,x_2,y_1,y_2\in\Sigma^*\}$$ In genereal, this substring $s$ is not unique. Therefore, I am looking for the maximal number $m(k,n)$ of different longest common substrings for an arbitrary pair of strings of length $n$. Formally: $$m(k,n)=\max\limits_{w_1,w_2\in\Sigma^n}\left|\left\{s\in A(w_1,w_2)\mid\forall x\in A(w_1,x_2):\;|s|\ge |x| \right\}\right|$$

Natural upper bound: It is easy to see, that $m(k,n)\le n$ since the maximal number of substrings of the same length for a strings of length $n$ is $n$ (for substrings of length $1$). For $n\le k$ we even achieve $m(k,n)=n$ (take a string $w_1$ which consists of different letters and $w_2$ the reverse string of $w_1$). For $n> k$ we conclude that $m(k,n)<n$, but from now on it seems to be difficult.

Lower bound: Based on De-Bruijn sequences it is possible to deduce a lower bound as follows:
As a conclusion of a paper of Lin et al, for each $m$ there are orthogonal De-Bruijn sequences $B_1(k,m)$ and $B_2(k,m)$ of length $k^m$, which means that the longest substring of $B_1(k,m)$ and $B_2(k,m)$ is of length $m$. The special property of (those) De-Bruijn sequences is, that each string of length $m$ is actually a substring (some of them by reading the De-Bruijn sequence cyclic). Therefore, both $B_1(k,m)$ and $B_2(k,m)$ containing $k^m-m+1$ different subtrings of length $m$ (acyclic) and for that reason there are at least $k^m-2m+2$ different longest common substrings for $B_1(k,m)$ and $B_2(k,m)$. So, for $n$ as a power of $k$, we get $$m(k,n)\ge n-2\log_kn+2$$ I'm quite sure we can achieve a very close result (caused by some rounding-issues) for each $n$.

But my question is, how tight are these bounds? I could imagine that orthogonal De-Bruijn sequences are already (asymptotic) worst case examples, i.e. $$m(k,n)\in n-\Theta(\log n).$$ But I am neither sure about this nor able to show it.

Any help is welcome!

Let $\ell$ be the length of the longest common substring. The number of longest common substrings $m$ is at most $$m \leq \min(k^\ell,n-\ell+1).$$ Let $x = \log_k n$. If $\ell \leq x-1$ then $m \leq n/k$. Otherwise, $m \leq n-\log_k n+2$. One checks that the latter bound is always worse, and so $m \leq n-\log_k n+2$.