論文http://webglimpse.net/pubs/suffix.pdfで理論を調べてみました
しかし、彼らが言うとき、私はちょっと迷っています
Ai を最初のバケットの最初の接尾辞 (つまり、Pos[0] = i) とし、Ai-h を検討します (ih < 0 の場合、Ai を無視して Pos[1] の接尾辞を取る、など)。 . Ai は最小の h シンボル文字列から始まるため、Ai-h はその 2h バケットの最初にあるはずです。
私はこの声明を理解することができません。ih < 0 の場合、Ai-h を無視できるのはなぜですか。フェーズ 1 で ih > 0 の場合、const 時間で位置を決定するには
1 つのサンプル impl はhttp://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/です。