後綴數組將索引給定字符串列表的所有後綴，但是如果您要索引所有可能的唯一子字符串，該怎麼辦？我在這個有點新的，所以這裏是我的意思的例子：完整的後綴數組
鑑於串
abcd
後綴數組索引（至少我的理解）
(abcd,bcd,cd,d)
我想索引（所有的子串）
(abcd,bcd,cd,d,abc,bc,c,ab,b,a)
是我想找的後綴數組嗎？如果是這樣，我該如何獲取所有的子字符串索引？如果不是，我應該在哪裏看？還有什麼我谷歌對比「所有子字符串」與「後綴子字符串」？
後綴數組完成你所需要的，因爲每個子字符串都是其中一個後綴的前綴。具體地，給出你的後綴數組
ABCD BCD CD d
，並假設你正在尋找串「BC」，那麼你就可以發現，尋找與「BC」開頭的所有後綴的（有在這種情況下只有一個「bcd」）。由於後綴數組按字典順序排序，查找共享某個前綴的所有後綴對應於跨後綴數組的二進制搜索，並且結果將是後綴數組的一個連續範圍的條目。
但是，使用後綴數組與輔助數據結構（如LCP（最長公共前綴）數組或小波樹）結合使用的優化搜索方法。有關這些方法的描述，請參見Navarro 2007年的調查（DOI 10.1145/1216370.1216372）。
爲了考慮下面提出的意見，我建議將每個後綴與代表的子字符串結合起來。在一個簡單的例子，如以上，這將是
4 abcd
3 bcd
2 bc
1 d
，因爲，例如，第一後綴「ABCD」表示4級的子串「一」，「AB」，「ABC」，「ABCD」。然而，在更復雜的例子，說字符串「abcabxdabe」，後綴數組的前兩個條目是
10 abcabxdabe
1 abe
因爲第二項表示子串「一」，「AB」和「安倍」 ，但是「a」和「ab」也由第一項表示。
如何計算一個條目表示的子字符串的數量？ - >後綴的長度減去它與前一個後綴共有的最長前綴的長度。例如。在「abe」示例中，即3（其長度）減2（「ab」的長度，它與前一個條目共享的最長前綴）。因此，這些數字可以通過後綴數組一次生成，如果還生成了LCP（最長公共前綴）數組，則速度更快。
下一步將產生累積計數：
10 abcabxdabe
11 abe
16 abxdabe
...
，然後找到一種有效的方式來利用累積計數。例如。如果你想按字典順序得到第13個子字符串，你必須找到第一個累計數大於或等於13的條目。這將是上面的「16 abxdabe」。然後刪除與前一個條目共享的前綴（產生「xdabe」），然後跳轉到第二個字符後面的位置（因爲前一個條目已經累計了11和13-11 == 2），所以你得到「 abxd「作爲第13個子字符串。
不錯，我想到了這一點，但是如果我想按照字典順序查找第n個子字符串，該怎麼辦。我不需要遍歷數組併爲非後綴子字符串添加條目嗎？因爲如果我檢索索引爲n的子字符串，這隻會計算後綴。我有什麼意義嗎？對不起，如果我不.. – Arjun 2012-02-22 07:12:10
我明白了，是的，這是有道理的。我誤解了你最初的「索引」的含義。但我相信你所要求的也可以使用稍微擴大的後綴數組來完成。具體而言，可以將數組中的每個後綴與一個數字組合起來，以指示它代表了多少個唯一的子字符串。它所表示的_substrings基本上是它所包含的前綴，減去前面後綴所代表的前綴。我將通過編輯答案來描述這些細節。 – jogojapan 2012-02-22 07:32:42
謝謝你的優雅的解決方案。我目前正在生成LCP數組，所以這看起來應該可以工作。非常感謝您的幫助，如果結果正常，我會通知您！ – Arjun 2012-02-24 06:45:38
您應該使用'Trie'的變體。實質上，如果你有ABCD，創建一個合併路徑的樹：root-> A-> B-> C-> D，root-> B-> C-> D，root-> C-> D和root - > d。現在，在每個節點都保留一個位置列表，其中字符串root - > .-> .->節點被觀察到。
謝謝，我會檢查出這種替代方法爲好。 – Arjun 2012-02-24 06:56:30
正如已經回答的那樣，子字符串是後綴的前綴。有時候你可能會想換一種方式來獲取前綴的後綴。
除此之外，目前還不清楚你在尋找什麼「獨特的子串」。我建議你查看單詞：類型，標記，最大值，超大值。在後綴數組文獻中找到這些應該沒有問題。
對我來說，有一種稍微有趣的方式來說相同的事情。一旦你得到你的後綴數組並運行，收集一系列關於後綴數組的文件並通過你的程序運行它們。你會看到在該領域使用了哪些技術詞彙。如果你睜大眼睛，你可能會得到一些驚喜。當然，如果你自己寫一篇論文，那麼通過後綴數組運行。不要忘記具有特殊屬性的數字類型的字符串。請享用！用後綴數組更好地生活！ – 2012-02-22 20:26:11
您的SA語料庫必須包含Abouelhoda et al。我會添加Kim等人的「線性後綴樹」論文。後者有一個很好的「文學評論」部分，這真的有助於通過Abouelhoda一些比較晦澀的部分。對於來自「休閒數學」視角的後綴數組，請閱讀KlausSchürman的書。 – 2012-02-22 21:20:35
您的SA語料庫必須包含Abouelhoda et al。我會添加Kim等人的「線性後綴樹」論文。後者有一個很好的「文學評論」部分，這真的有助於通過Abouelhoda一些比較晦澀的部分。對於來自「休閒數學」視角的後綴數組，請閱讀KlausSchürman的書。 （特別提示）查看加斯菲爾德在加州大學戴維斯分校的錄像帶講座。 – 2012-02-22 21:40:34
看到這個： http://stackoverflow.com/questions/2560262/generate-all-unique-substrings-for-given-string – 2012-02-22 06:05:29