主題
題目連結(jié)：
題目意譯：
一個長度 k 且索引值從 0 開始之字串 s，其雜湊值是由以下函數(shù)並給定兩整數(shù) p 和 m 而計算出來：
hash(s, p, m) = (val(s[0]) × p ^ 0 + val(s[1]) × p ^ 1 + ... + val(s[k-1]) × p ^ (k-1)) mod m。
其中 val(s[i]) 代表 s[i] 位於字母表中的索引值，也就是從 val('a') = 1 到 val('z') = 26。
你被給定一字串 s 以及整數(shù) power 、 modulo 、 k 以及 hashValue。回傳 sub，其為 s 中第一個長度 k 的子字串使得 hash(sub, power, modulo) == hashValue。
測資之生成滿足答案必定永遠(yuǎn)存在。
一個子字串為一字串中的一個非空連續(xù)字元序列。
限制：
1 ≦ k ≦ s.length ≦ 2 × 10 ^ 4
1 ≦ power, modulo ≦ 10 ^ 9
0 ≦ hashValue < modulo
s 只由小寫英文字母組成。
測資之生成滿足答案必定永遠(yuǎn)存在。
範(fàn)例測資：
範(fàn)例 1：
輸入： s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
輸出： "ee"
解釋： "ee" 的雜湊值可以藉由 hash("ee", 7, 20) = (5 × 1 + 5 × 7) mod 20 = 40 mod 20 = 0 計算出來。
"ee" 是第一個長度 2 的子字串其有著雜湊值 0。因此我們回傳 "ee"。
範(fàn)例 2：
輸入： s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
輸出： "fbx"
解釋： "fbx" 的雜湊值可以藉由 hash("fbx", 31, 100) = (6 × 1 + 2 × 31 + 24 × 312) mod 100 = 23132 mod 100 = 32 計算出來。
"bxz" 的雜湊值可以藉由 hash("bxz", 31, 100) = (2 × 1 + 24 × 31 + 26 × 312) mod 100 = 25732 mod 100 = 32 計算出來。
"fbx" 是第一個長度 3 的子字串其有著雜湊值 32。因此我們回傳 "fbx"。
注意到 "bxz" 有同樣有著雜湊值 32，但是它出現(xiàn)於 "fbx" 之後。
解題思維：
本題的核心精神很簡單——滑動視窗（Sliding Window，如這題），也就是利用已知的一個子字串的雜湊值去「快速地」算出「相鄰」子字串的雜湊值（例如在範(fàn)例一中，用 "ee" 的雜湊值 32 算出 "le" 或是 "et" 的雜湊值）。
不過在本題中，從左至右比從右至左難上非常地多（等下可以看到原因）。因此我們可以先算出 s 最右側(cè)的、長度 k 之子字串（例如範(fàn)例一的 "de" 或是範(fàn)例二的 "aad"）的雜湊值。接下來的問題就是要怎麼推得左邊相鄰的子字串。方法如下：
（以下將 val(s[i]) 等表示法簡化成 s[i]，僅為方便起見）
假設(shè)已知從 s[i] 開始的長度 k 子字串之雜湊值，可以看到其值 X 為：
(s[i] × p ^ 0 + s[i + 1] × p ^ 1 + ... + s[i + k -1] × p ^ (k-1)) mod m
而將其與 s[i - 1] 開始的長度 k 子字串之雜湊值 Y 比較：
(s[i - 1] × p ^ 0 + s[i] × p ^ 1 + ... + s[i + k - 2] × p ^ (k-1)) mod m
可以看到上面藍(lán)色的是「少掉的」、紅色則是「多出的」，因此可以推得
Y = (p × X) - (s[i + k -1] × p ^ k) + (s[i - 1] × p ^ 0)
可以看到我們只要預(yù)先計算出 p ^ k，就可以在每次把滑動視窗往左移動時便可以在 O(1) 時間內(nèi)算出下一個雜湊值。
而因為我們是由右至左，而非由左至右（即原先的順序），因此我們現(xiàn)在要找的是「最後一個」雜湊值等於 hashValue 的子字串。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
