再解字串有關的題目時, 通常suffix array 是一個很有用的方法.
suffix array 就是將一個字串的所有後綴經過"排序"存到陣列裡.
例如 : 字串abagabal
它的suffix 就有
abagabal
bagabal
agabal
gabal
abal
bal
al
l
排序後變成
abagabal
abal
agabal
al
bagabal
bal
gabal
l
這樣擺放的好處是"搜尋變快", 例如給另一個字串bal , 要問bal 是不是存在上面的abagabal 裡頭,
其實就是對suffix array 做binary search
過程 : 因為後綴陣列大小為8, 先從(0+7)/2 = 3開始發現al < bal , 所以變成(4+7)/2 = 5,bal == bal.
那接下來要討論的是
怎麼樣才可以快算的建出後綴陣列 ?
天真的作法 (naive method )
1. 先得到所有的後綴
2. 對所有的後綴排序
3. 結束
1. 如果是新手的話, 很容易就會先利用C++ 函式substr來做出後綴,但千萬別這麼做,
如果你那樣做的話, 時間複雜度在 (1) 就會是O(n^2) 了. 那還不如不要建後綴陣列.
這裡利用pointer的技巧就可以了.
例如 char str[1000]; char *suffix[1000];
for(i = 0 ;i < 1000 ; i++) suffix[i] = str+i;
2. 做sort , 就呼叫 C++ sort 或C qsort.
天真的作法在於(2) sort 會花到O(n^2logn), 假設sort 花O(nlogn), 但string 的長度是n的話.
天真的作法不是不好, 有時在解題時, 它反而比較沒有限制, 要實際解題目就知道了!
接下來要進入經典演算法 , 我知道在處理suffix array 的演算法是
A. prefix doubling algorithm O(nlogn)
B. DC3 algorithm O(n)
我目前只code 過 (A) 所以下面是以(A) 為主.
在步驟(2) 時, sort 花太多時間.
prefix doubling algorithm 同樣也要sort , 但它是sort 字串的每個字元.
什麼意思?
例如 : abagabal
對每個字元sort 排名
a 1
b 2
a 1
g 3
a 1
b 2
a 1
l 4
同樣的字完有相同的排名( 排名表示以某字元為首的後綴長度為1 )
接下來得到長度為2, 過程會先得到
a 12
b 21
a 13
g 31
a 12
b 21
a 14
l 40
例如第一個a 是12 因為a 後面的字是b , b 排名2, 而a 本身是1
所以整理之後得到
a 1
b 4
a 2
g 5
a 1
b 4
a 3
l 6
這是後綴長度為2 的排名
繼續 得到長度為4如下
a 12
b 45
a 21
g 54
a 13
b 46
a 30
l 60
( 後面沒字母就補0)
同樣的從長度為2 要得到長度為4 , 是把2個相鄰長度為2 的合併, 例如 a 12 是因為a 本身排名為1, 而a 後兩個字母是a 但此a 排名
為2 所以得到12.
整理之後
a 1
b 5
a 3
g 7
a 2
b 6
a 4
l 8
繼續得到長度為8
a 12
b 56
a 34
g 78
a 20
b 60
a 40
l 80
整理後
a 1
b 5
a 3
g 7
a 2
b 6
a 4
l 8
這就是長度為8 的後綴排名.
比較
abagabal
bagabal
agabal
gabal
abal
bal
al
l
==> sort 後得到
abagabal
abal
agabal
al
bagabal
bal
gabal
l
a 1
b 5 ==> bagabal 在sort 後的第五位
a 3
g 7
a 2
b 6
a 4
l 8
prefix doubling algorithm 的精神是: 1個的結果=> 2個的結果 => 4個的結果 => 8個的結果. ( 單位: 後綴長度)
通常suffix array 會搭配longest common prefix array (LCPA).
LCPA 紀錄後綴字串A, 與前者之間的共同最長前綴.
例如
LCPA
abagabal 0
abal 3
agabal 1
al 1
bagabal 0
bal 2
gabal 0
l 0
接下來又出現新的問題了!
如果直接計算LCPA 的值會花到O(n^2). 假設字串長度為n, 字串有n 個
計算LCPA array 只需要O(n).
先注意一個特性
如果是排名第一的後綴那就直接是0
abagabal => 0
再來考慮bagabal, 它的排名前一名是al , 比較兩者得0
所以bagabal => 0
再來考慮agabal, 排名前一個是abal
得到agabal => 1
再來gabal, 排名前一個是bal , ( 注意 : (agabal,abal) = 1+(agabal,bal) )
得到gabal => 0
再來abal , 排名前一個是abagabal
得到abal => 3
再來bal, bagabal ( 從上面注意其實我們只要從index 2 (index 從0開始) 開始比較就可以了, 因為
(abal,abagabal) = a + (bal,bagabal) , 既然, abal 得到3, bal 至少會是2, 所以只要從字母l 開始比較 )
所以bal中的l 與bagabal中的g 開始比較, 因為b!=g不同
因此bal => 2
再來al, 排名前一個 agabal
因為bal是2所以從index 1開始
al 中的l != agabal 的g
所以al=> 1
最後l與gabal得到
l => 0
留言列表
