瞭解執行DC3/Skew算法以創建後綴數組線性時間

Question

我想了解Karkkainen，P. Sanders的線性時間後綴數組創建算法的實現。算法的細節可以找到here。

我設法理解整體概念，但未能與提供的實現相匹配，因此無法清楚地理解它。

這裏是最初的代碼路徑令我困惑。

作爲每紙：N0，N1，N2表示三聯體編號開始在爲i mod 3 =（0,1,2）

由於每個代碼：N0 =（N + 2）/ 3中，n1 = （n + 1）/ 3，n2 = n/3; =>這些初始化是如何派生的？

作爲每紙：我們需要創建T`這是三聯體級聯在爲i mod 3 = 0

由於每個代碼：N02 = N0 + N2; s12 = [n02] ==> n02怎麼樣？它應該是n12，即n1 + n2。對於（int i = 0，j = 0; i < n +（n0 - n1）; i ++）用三元組填充s12使得i％3！= 0; =>爲什麼循環運行n +（n0 - n1）次？它應該是簡單的n1 + n2。不應該？

我不能因爲這些:(請幫助進行

Answer 1

看看下面的例子，其中輸入的長度爲n = 13：

STA | CKO | WER | FLO | W 

按代碼：N0 =（N + 2）/ 3中，n1 =（N + 1）/ 3，N 2 = N/3; =>如何對這些initialisations已經導出

注意，我MOD3三胞胎的數量？ = 0是n/3，如果n mod3 = 0且否則爲n/3 + 1（如果n mod3 = 1或n mod3 = 2）。在當前示例中，n/3 = 4，但由於最後一個三元組「W」未完成，因此不會計入整數除法。直接進行此計算的「技巧」是使用（n + 2）/ 3。實際上，如果n mod3 = 0，那麼整數除法（n + 2）/ 3和n/3的結果將是相同的。但是，如果n mod3 = 1或2，則（n + 2）/ 3的結果將是n/3 + 1。這同樣適用於n1和n2。

根據代碼：n02 = n0 + n2; s12 = [n02] ==> n02怎麼樣？它應該是n12，即n1 + n2。 按照代碼：for（int i = 0，j = 0; i < n +（n0 - n1）; i ++）用三元組填充s12，使得i％3！= 0; =>爲什麼循環運行n +（n0 - n1）次？它應該是簡單的n1 + n2。不應該？

這兩個問題都有相同的答案。在我們的例子中，我們就會有一個緩衝B12這樣的：

B12 = B1 U B2 = {TA KO ER LO} 

所以你首先後綴進行排序，並與B12的後綴數組，其中有8個元素結束。要進行合併步驟，我們首先需要計算B0的後綴數組，這是通過對元組（B0（i），rank（i + 1））進行排序而獲得的...但是，這在其中最後三重僅具有一個元素（W）的混凝土的情況下有一個問題，因爲秩第（i + 1）B 0的最後一個元素沒有被定義：

B0 = {0,3,6,9,12} 

其中按字母順序排序導致

SA0 = {3, 9, 0, ?, ?} 

由於指數6和12包含「W」，這是不夠的，按字母順序排序，我們需要檢查哪些先行在排名表，讓我們檢查他們的後綴等級..哦，等待！等級（13）沒有定義！

這就是爲什麼當最後一個三元組只包含一個元素（如果n mod3 = 0）時，我們在輸入的最後一個三元組中添加了一個虛擬0。因此，那麼B12的大小是n0 + n2，無論n1的大小如何，並且如果B0大於B1（在這種情況下n0-n1 = 1），則需要向B12添加額外的元素。

希望它很清楚。