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。