suffix array 演傳法－a301400的部落格

子序列只要順序不變的
子字串則是一定要連續的一段
例如:(T,A,L,E)是T,E,N,T,A,C,L,E的子序列不是子字串

最長重複子字串還分成兩種
1.可重複
2.不可重複
例如:a,b,a,b,a,b
可重複最長是(a,b,a,b)
不可重複最長是(a,b)
這兩種的解法都可以用一種資料結構:後綴數組(suffix array)+求最長共同前綴(LCP)來解
後綴數組概念是宣告一個陣列sa[]
sa代表所有後綴字典序第i名的開始點
例如:1 3 1 3 4
後綴分別是
1 3 1 3 4
3 1 3 4
1 3 4
3 4
4
排序後
1 3 1 3 4(從第1個元素開始的後綴)
1 3 4    (從第3個元素開始的後綴)
3 1 3 4 (從第2個元素開始的後綴)
3 4       (從第4個元素開始的後綴)
4          (從第5個元素開始的後綴)
sa[]=(1,3,2,4,5)
ra[]=(1,3,2,4,5) (sa[ra[ i ]]=i也就是ra為sa的反函數)
lcp的概念就是求出任兩個後綴得最長共同前綴
例如:lcp(sa[1],sa[2])=2
因為1 3 1 3 4跟1 3 4前兩項一樣
實作時
會設一個數組h[]
h[ i ]=lcp(sa[ i ],sa[i-1]);
要求lcp(i,j)時只要求min(h[ra[ i ]+1]~h[ra[j]])  設ra[j]>ra[ i ]
如果要降低複雜度可以轉化成RMQ問題

-----------------------------------------------------------------------------------------------------------------------

一個字串的每個後綴的開頭，正是字串匹配時， P 的每個對齊位置。儘管後綴是指字串的後端，然而後綴用於字串匹配時，思想上是連結到後綴的前端。

T: mississippi
P: issi

all suffixes of T:
   mississippi, ississippi, ssissippi, ...
   
string matching:
   0             1            2
   mississippi   ississippi   ssissippi   ...
   issi          issi         issi

以後綴為觀點，便產生了一種字串匹配的手法：第一步、先列出 T 的全部後綴，第二步、尋找哪些後綴的前綴恰是 P 。

選擇一個適當的資料結構，儲存 T 的全部後綴，並且預先排序 T 的全部後綴，如此尋找 P 的速度就會更快。

參考:

演算法 http://www.csie.ntnu.edu.tw/~u91029/StringMatching2.html