Longest Common Prefix Array

Question

Following is the Suffix array and LCP array information for string MISSISSIPPI. I know that LCP gives information about the lenght of the longest common prefix between str[i - 1] and str[i]. How Do I get longest common prefix length between any two arbitrary suffixes of this string. For example, I want longest common prefix between MISSISSIPPI and ISSIPPI

SA  LCP
12  0     $
11  0     I$
8   1     IPPI$
5   1     ISSIPPI$
2   4     ISSISSIPPI$
1   0     MISSISSIPPI$
10  0     PI$
9   1     PPI$
7   0     SIPPI$
4   2     SISSIPPI$
6   1     SSIPPI$
3   3     SSISSIPPI$

Answer 1

From http://en.wikipedia.org/wiki/Suffix_array, we have that "The fact that the minimum lcp value belonging to a consecutive set of sorted suffixes gives the longest common prefix among all of those suffixes can also be useful." So in your case, the LCP between MISSISSIPPI and ISSIPPI is min(4, 0) = 0.

You can find the minimum in a range in time O(1) via http://en.wikipedia.org/wiki/Range_Minimum_Query, and there is a lot of info on alternative approaches if you look at the TopCoder link there.