後綴數組使用曼伯邁爾斯算法

Question

我試圖通過理論在紙張http://webglimpse.net/pubs/suffix.pdf

去，但我有點失去了當他們說

讓艾是在第一個桶中的第一個SUF網絡X（即Pos [0] = i），並考慮Ai-h（如果ih爲< 0，那麼我們忽略Ai並且取Pos [1]的後綴，等等）。由於Ai以最小的h符號字符串開始，因此Ai-h應該是第一個2h桶。

我無法理解這種說法。爲什麼Ai-h可以忽略如果i-h < 0.當階段1中i-h> 0時，常位時間內的位置是如何確定的？

一個樣品IMPL是http://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/

Answer 1

我強烈建議，而不是試圖瞭解C++代碼，通過這個Python implementation of the Manbers-Myers suffix array construction algorithm走路，手，一個簡單的5個字符的例子。

由於Python版本只有大約15行代碼，因此很容易遵循。

即使您不理解Python，也應將其視爲僞代碼，並將Google視爲您不明白的語法。

就我個人而言，我手工通過一個5個字符的字符串，這足以幫助我瞭解該算法是如何工作的。