這邊提供後綴數組DC3算法的模板，他是一個能在線性時間\(\ord N\)內求得後綴數組的演算法，注意這邊傳入的陣列s及sa長度必須是字串長的3倍以上，因為DC3會用到大量的記憶體，而且會利用傳入的陣列s的空間進行計算，因此傳入的陣列s必須是int範圍，而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過，因此必須給字串先做以下處理:
假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2
因為是遞迴的關係，所以常數很大，但在大數據的時候比倍增法快
關於DC3演算法的介紹請看這兩篇文章:
http://ching.im/post/algorithm/difference-cover-modulo-algorithm
《后缀数组——处理字符串的有力工具》
如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/
在傳入的參數中最後一個A為最大的字元+1通常設為'z'+1
以下提供模板(其實code挺短的):
沒有留言:
張貼留言