最長共通接頭辞配列

Question

以下は、MISSISSIPPIのSuffix arrayおよびLCP arrayの情報です。私はLCPが、str[i - 1]とstr[i]の間の最も長い共通接頭辞の長さに関する情報を提供していることを知っています。どのようにしてこの文字列の任意の2つの接尾辞の間に最も長い共通接頭語長を取得するのですか？例えば、私はhttp://en.wikipedia.org/wiki/Suffix_arrayからMISSISSIPPIと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

間の最長共通接頭辞をしたい、我々は最小LCP値がソートされたサフィックスの連続したセットに属するという事実は、これらのすべての中で最長の共通のプレフィックスを与える」ことを持っています接尾辞も便利です。」あなたのケースでは、MISSISSIPPIとISSIPPIの間のLCPはmin（4,0）= 0です。

http://en.wikipedia.org/wiki/Range_Minimum_Queryで時間O（1）の範囲で最小値を見つけることができます。そこにあるTopCoderリンクを見ると、別の方法があります。