<p>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$.</p>

CC BY-SA 3.0
2014-11-29T00:46:31.007Z
2014-11-29T00:46:31.007Z
Yuval Filmus
<p>Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow">longest common substring problem</a> 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 <strong>maximal number $m(k,n)$ of different longest common substrings</strong> 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|$$</p>

<p><strong>Natural upper bound</strong>: 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&gt; k$ we conclude that $m(k,n)&lt;n$, but from now on it seems to be difficult.</p>

<p><strong>Lower bound</strong>: Based on <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence" rel="nofollow">De-Bruijn sequences</a> it is possible to deduce a lower bound as follows:<br>
As a conclusion of a <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6BA27E08E30C5DFDDA269211D63B232D?doi=10.1.1.307.3029&amp;rep=rep1&amp;type=pdf" rel="nofollow">paper of  Lin et al</a>, for each $m$ there are <em>orthogonal</em> 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$.</p>

<p>But my question is, <strong>how tight are these bounds?</strong> 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.</p>

<p>Any help is welcome!</p>

<co.combinatorics><lower-bounds><upper-bounds><worst-case>
Number of different longest common substrings
Danny
# Number of different longest common substrings

(Asked by: username_0 on 2014-11-28)

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](http://en.wikipedia.org/wiki/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)

**Lower bound**: Based on [De-Bruijn sequences](http://en.wikipedia.org/wiki/De_Bruijn_sequence) it is possible to deduce a lower bound as follows:  
As a conclusion of a [paper of Lin et al](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6BA27E08E30C5DFDDA269211D63B232D?doi=10.1.1.307.3029&rep=rep1&type=pdf), 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!

**Tags:** co.combinatorics, lower-bounds, upper-bounds, worst-case


---

## 1 answers

### Answer by username_1 on 2014-11-29. Score: 3 | Accepted answer

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


---

