3
$\begingroup$

Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ complexity. Lets call this operation as prefix-suffix match.

I want to calculate prefix-suffix match length for all suffixes of a string. Now the naive algorithm which doesn't take into account that all the strings for which I am doing this operation are related has $O(n^2)$ complexity. Now my question is can we do this in better complexity.

Note that what I want is similar to LCP array of a slightly modified suffix array. Where the suffixes are sorted based on length instead of lexicographic ordering.

$\endgroup$
  • $\begingroup$ i am probably misunderstanding this sou you want to compute $lcp(S[i],S[i+1])$ in O(|S|) time for all $0\leq i \leq |S|$ or ...?? PS $S$ is a string $\endgroup$ – user6697 Oct 22 '13 at 12:10
  • 1
    $\begingroup$ Allocate an array of $n$ integers, fill it backwards with a single iteration ... am I missing anything? $\endgroup$ – reinierpost Oct 22 '13 at 12:30
  • $\begingroup$ the result of "prefix-suffix" operation is always a string that is repetition of one character (i.e. $c^*$, $c$ a character). Is that sufficient? $\endgroup$ – Parham Oct 22 '13 at 16:44
  • $\begingroup$ @user6697 Who said O(|s|). I am happy with O(|s| log |s|) too. $\endgroup$ – Satvik Oct 22 '13 at 17:07
  • $\begingroup$ @MahmoudAlimohamadi Yes. You are right. I suppose, I misrepresented what I want. I will ask another question stating what I exactly want. $\endgroup$ – Satvik Oct 22 '13 at 17:10
1
$\begingroup$

Expanding on reinierpost's comment, here is how to do it in linear time. Every word $w$ can be decomposed as $w = a_1^{k_1} a_2^{k_2} \cdots a_l^{k_l}$, where $a_i \neq a_{i+1}$ and $k_i \geq 0$. This is just decomposition into runs. The LCP of $w$ and its shift is simply $a_1^{k_1-1}$.

In view of this, here is how to compute the answer for all suffixes of a word $w$ in linear time. We go over the array backwards, populating an array $K$ using the following algorithm:

  1. $K_n = 1$.
  2. For $i = n-1,\ldots,0$:
    1. If $w_i = w_{i+1}$, $K_i = K_{i+1} + 1$, otherwise $K_i = 1$.

The answer for the suffix starting at $w_i$ is $w_i^{K_i-1}$.

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