2007/04/29

Z-Value 備忘

首先要提出的一點:若採用 STL 的左閉右開慣例並讓字元編號從 0 開始,那麼整個演算法(包括右護法 R、左護法 L)的表述都會變得相當乾淨。我的定義依照 C/C++ 字串的慣例(字元編號從 0 開始,區間採用左閉右開),而且 L(i) 的定義可能比較符合原意(我還沒去思考隨機客投影片的定義、隨機客口頭的定義(所謂原意)、和我的定義三者是否等價):

其中 L(i) 取 min 應該只是為了讓它是 well-defined,實作上不取應該無妨。我上 Amazon.com 看 Gusfield《Algorithms on Strings, Trees, and Sequences》字串的定義,s[i..j] = s[i] s[i + 1] ... s[j],i 和 j 之間是兩個點,而我的 notation 是三個點,這和 Ruby 的語法完全一致。不過隨機客的 notation 是 s[i...j] = s[i] s[i + 1] ... s[j] XD。

從 i 之前所有的 Z-values 和 r = R(i - 1)、l = L(i - 1) 算出 i 位置的三個函數值時,分為三種狀況。第一種是 r <= i,此時完全無法從已知推斷未知,所以只能用 naïve 的方法比對計算 Z(i)。第二大類是 r > i,以 i 為中心,將 s[l...r] 分為 s[l...i] 和 s[i...r] 兩段,此時我們有以下的已知條件:

這個狀況下的第一個 subcase 可如下推演:

第二個 subcase:

總之可以「代數地」處理此事,而且因為左閉右開,所以完全不需處理 offset-by-one 的問題,很乾淨。詳細狀況連同實作我以後再補,今日不宜花太多時間 XD。

--
只是先記下來備忘 XD。

Labels:

<< 回到主頁