# String matching for all suffixes

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.

• 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 – user6697 Oct 22 '13 at 12:10
• Allocate an array of $n$ integers, fill it backwards with a single iteration ... am I missing anything? – reinierpost Oct 22 '13 at 12:30
• 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? – Parham Oct 22 '13 at 16:44
• @user6697 Who said O(|s|). I am happy with O(|s| log |s|) too. – Satvik Oct 22 '13 at 17:07
• @MahmoudAlimohamadi Yes. You are right. I suppose, I misrepresented what I want. I will ask another question stating what I exactly want. – Satvik Oct 22 '13 at 17:10

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