3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.