# Python-LeetCode 581 第18招 String (II)
## Palindrome
Palindrome(迴文)是一個左右對稱的字串，也就是由左往右念與由右往左念都一樣，其長度可能是奇數也可能是偶數，例如abcba與abbbba。Palindrome很常出現在字串題中，每一題要用的方法可能不相同，基本上只是一種出題形式。
以下是一個很基本的題目。
[(題目連結) 5. Longest Palindromic Substring (Medium)](https://leetcode.com/problems/longest-palindromic-substring/description/)
在一個字串中找出最長的palindrome，這題的測資不大，可以用基本的方法來做。
迴文如果從左端往右找，會不知要比對的對象在哪裡，通常比較好的處理的方式是從中心往兩邊找，對一個中心點，最壞linear time就可以找出左右對稱的最長範圍，但是要注意奇數與偶數。枚舉所有可能的中心點，總花費時間是$O(n^2)$，以下是範例程式。
我們在前後加上不可能出現的字元，用意是省略邊界檢查(sentinel)。第7 ~ 11行是找奇數長度的；第13 ~ 17行是找偶數長度的。
```python=
# trival O(n^2) alg, try each center
class Solution:
def longestPalindrome(self, s: str) -> str:
s = '['+s+']'
# odd length
longest = ""
for c in range(1,len(s)-1):
r = 1
while s[c-r] == s[c+r]: r += 1
if r+r-1 > len(longest):
longest = s[c-r+1:c+r]
# even length, center between i and i+1
for i in range(1,len(s)-2):
r = 0
while s[i-r] == s[i+1+r]: r += 1
if r+r > len(longest):
longest = s[i-r+1: i+1+r]
return longest
```
找最長的palindrome有一個很有趣的演算法：
**Manacher Algorithm**
網路上可以找到一些教學與說明的文件，[CP-Manacher](https://cp-algorithms.com/string/manacher.html) 這一篇說得蠻清楚易懂的，有興趣的讀者可以參考。
它的主要精神跟KMP很像，也是避免重複的計算。簡單來說，假設我們已經算出所有中心點小於 i 的最長迴文長度，在計算中心點為 i 的最長迴文時，若 i 被包含在一個以 c 為中心的迴文區間，那麼 c 的左邊有一段與 i 附近完全對稱的字串，而且左邊那一段的迴文長度已經是算過而可以直接拿來運用的。詳情還是參考上述文件，這個演算法最後的結果是非常乾淨簡短的，除此之外，也有一個有趣的地方，原始的演算法只能算長度奇數的迴文，但透過一個有趣的技巧來算偶數長度的迴文。
以下是範例程式，時間複雜度是線性時間。我們把Manacher演算法單獨寫一個函數，計算最長迴文的前置處理也寫一個函數。
```python=
# with sentinel at head and tail
def manacher(s): # return odd radius
radius = [1]*len(s)
left = right = 1
for i in range(1,len(s)-1):
if i < right:
radius[i] = min(right-i, radius[left+(right-i)])
while s[i-radius[i]] == s[i+radius[i]]:
radius[i] += 1
if i+radius[i] > right:
left,right = i-radius[i],i+radius[i]
#end for
return radius[1:len(s)-1]
def palindrome(s): # find longest palindrome
t = '#'.join(list('['+s+']'))
r = manacher(t)
# i at s[i//2]
i = r.index(max(r))
return s[(i-r[i]+2)//2: (i+r[i])//2]
class Solution:
def longestPalindrome(self, s: str) -> str:
return palindrome(s)
```
下面這題有點難。
[(題目連結) 1960. Maximum Product of the Length of Two Palindromic Substrings (Hard)](https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/)
題目是說在一個字串中找到兩個長度為奇數且不相交的palindrome，使得兩個長度的乘積為最大。
長度為奇數這個條件看起來怪怪的，如果了解馬拉車(Manacher algorithm)就會知道，因為馬拉車算法的原型就是做奇數長度的palindrome，本題需要用馬拉車，但因為題目已經夠難了，不想讓題目搞得太複雜目雖然直接限定奇數長度。
首先，我們跑馬拉車算法，可以在線性時間找出所有迴文，這些得到的迴文形式是$(i, radius[i])$，代表以 $i$ 為中心的最大迴文是$(i-radius[i], i+radius[i])$。第二個問題是要找出不相交而長度乘積最大的兩個，因此，不能只是找兩個最大的相乘。
我們知道迴文是對稱的，所以對於 $i$，在半徑$radius[i]$以內都是迴文，也就是說，對於$j\le radius[i]$，$(i-j, i+j)$都是迴文。我們可以這麼做：對每一個位置 $i$，找出在 $i$ 左邊的最大迴文長度$lmax[i]$，同樣的，找出在右邊的最大迴文長度$rmax[i]$，然後，在線性時間可以找出答案
$\max_{i}\{ lmax[i]\times rmax[i+1]\}$。
剩下的問題是如何在線性時間找出 $lmax$ 與 $rmax$。這兩個找法是類似的。我們用下面的範例程式來解說 $lmax$ 的計算方式。
第8 ~ 19行是馬拉車算法，不再說明。第20行是我們要算的 $lmax$ 的初始。我們由左往右逐步掃描每一個中心點 $i$，用 $pmax$ 紀錄目前找到的最長迴文長度，對於中心點 $i$，它的最大迴文長度是$2\times radius[i]-1$，如果這個值不超過 $pmax$，我們就略過它不必處理。如果比 $pmax$ 大，我們要更新某些 $lmax$ 的值，但必須留意，這個迴文不是從 $i$ 就開始這麼大，而是往右逐步變大，所以，我們只更新它比 $pmax$ 大的位置，這是第25 ~ 26行的意思。第27行更新 $pmax$ 的值。在結束之後，第29行再跑一個 prefix maximum 就得到 $lmax$。
相同的方法可以求 $rmax$，為了方便，我們並非從右往左計算，而是將原順序倒反之後，將剛才的程式碼再抄一遍，計算答案時，$rmax$ 的 index要反過來。
時間複雜度方面，馬拉車是線性時間，唯一的問題是找 $lmax$ 這樣做是$O(n)$嗎？第22與第25行的雙迴圈的複雜度並不明顯。內迴圈的複雜度其實是正比於新的最大迴文長度減去舊的最大迴文長度，由於我們只處理長度變大的狀況，所以全體的總和是每次變量的總和，也就是累積變化量，而累積變化量不超過$O(n)$。所以整個程式的時間複雜度是$O(n)$。
```python=
class Solution:
# manacher algorithm find palindrome, only odd length
# left and right sweep to find the longest before left and after right
def maxProduct(self, s: str) -> int:
n = len(s)
if n==2: return 1
#manacher algorithm
s += '[]' # sentinel
radius = [1]*n # (c-r, c+r)
left = right = 0
for c in range(1,n):
if c < right:
radius[c] = min(right-c, radius[left+right-c])
else:
radius[c] = 1
while s[c-radius[c]] == s[c+radius[c]]:
radius[c] += 1
if c+radius[c] > right:
left,right = c-radius[c],c+radius[c]
lmax = [1]*n # longest palindrome before i
pmax = 1 # current max
for i in range(n): #linear time only update the larger
if radius[i]+radius[i]-1 > pmax:
# 2(j-i)+1>pmax
for j in range((pmax-1)//2+1, radius[i]):
lmax[i+j] = 1+j+j
pmax = radius[i]+radius[i]-1
# prefix max
for i in range(1,n): lmax[i] = max(lmax[i],lmax[i-1])
# find rmax, reverse and do it again
radius = radius[::-1]
rmax = [1]*n
pmax = 1
for i in range(n): #linear time only update the larger
if radius[i]+radius[i]-1 > pmax:
for j in range((pmax-1)//2+1, radius[i]):
rmax[i+j] = 1+j+j
pmax = radius[i]+radius[i]-1
for i in range(1,n): rmax[i] = max(rmax[i],rmax[i-1])
ans = max(lmax[i]*rmax[n-1-(i+1)] for i in range(n-1))
return ans
```
[(題目連結) 1745. Palindrome Partitioning IV (Hard)](https://leetcode.com/problems/palindrome-partitioning-iv/)
題目是說給一個字串 s，回答 s 可否完美的切割成3個迴文。也就是是否 s = p + q + r，其中 p, q, r 都是迴文。本題輸入字串長度不超過2000。
由於輸入字串的長度不至於太長，我們可以採用以下的方法：
1. 先找出所有的迴文，包含偶數與奇數長度；
2. 將迴文分三類，左端從0開始的放在 head，右端接在字串尾的放在 tail，其餘的放在 mid，其中 head 與 tail用set()紀錄迴文的另外一端位置；
3. 對於每一個mid中的迴文，檢查他的左右端可否剛好接到 head 與 tail 中所記錄的位置構成一個完美分割。
以下是範例程式，第5行字串尾端放兩個不會出現的字元當做邊界的哨兵，留意Python的 list.[-1] 是最後一個，這樣可以省略邊界檢查。第7 ~ 12行找出所有奇數長度的迴文；而第14 ~ 18行找出所有偶數長度的迴文。接著第20 ~ 23行把所有迴文掃一遍，如左端在0的就將右端存入 head，如果右端在$n-1$的就把左端記入 tail，其他的放入 mid。
最後對mid中的左右端做檢查，看看能否構成完美分割。留意head 與 tail 用集合來做以減少查詢的時間。
時間複雜度是$O(n^2)$，因為迴文的數量上限。
```python=
class Solution:
def checkPartitioning(self, s: str) -> bool:
n = len(s)
palin = []
s += '][' # sentinel
# all palindrome centered at i
for i in range(n):
palin.append((i,i))
j,k = i-1,i+1
while s[j]==s[k]:
palin.append((j,k))
j -= 1; k += 1
# all palindrome centered at i,i+1
for i in range(n-1):
j = i+1
while s[i]==s[j]:
palin.append((i,j))
i -= 1; j += 1
head,tail,mid = set(),set(),[]
for i,j in palin:
if i==0: head.add(j)
elif j==n-1: tail.add(i)
else: mid.append((i,j))
for i,j in mid:
if i-1 in head and j+1 in tail: return True
return False
```
大部分迴文的問題是找substring，但下面這題是找subsequence。
[(題目連結) 1771. Maximize Palindrome Length From Subsequences (Hard)](https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/)
題目是說給兩個字串 word1 與 word2，要從第兩個字串中各找一個非空的subsequence，然後把它們接在一起(第一個在前)，請問這樣構成的迴文最長的長度是多少。
我們先看一個簡化的問題：**如何找出一個字串 s 中最長的迴文子序列**。
答案其實很簡單：LCS(s, s[::-1])，也就是說，原序列與其反轉序列的Longest common subsequence。
那麼，這一題是否將輸入的兩序列串接後，求與自己反轉序列的LCS就好了呢？答案是否定的。這題有個陷阱，就是題目要求兩個字串找出的都必須是非空，也就是LCS不可以只存在其中一個字串中。為了保證這件事，我們使用了一個前置處理：
將 word1 的前綴中完全沒有出現在 word2 中的字元刪除，保證 word1[0] 一定出現在 word2 中；同樣的，將 word2 後綴中完全沒有出現在 word1 中的字元刪除，保證 word2[-1] 一定出現在word1中。
**Claim: 若w = w1 + w2且 w1[0] 出現在 w2 中，則必存在 s = LCS(w, rev(w))包含至少一個字元來自 w2**。
這個證明很容易，假設 s 不包含任何 w2 中的字元，因為 s 為最長，s[0] = w1[0]，且 s[0] 所對應的 s[-1] 在 w1中。但已知 s[0] 存在 w2 中，也就是存在某個 w2[i] 滿足s[0] = s[-1] = w2[i]，我們可以將 s[-1] 改為 w2[i]。
同樣的，只要 w2 的字尾存在於 w1 中，LCS就一定會包含 w1 的某個字元。
有關LCS的求法，可參考[Python-LeetCode 581 第15招 Dynamic Programming II：二維](/fAoEHeN4Tum27Wh30N-RYQ)中的LeetCode 1143題的解法說明。所以我們可以得到以下的範例程式。第6 ~ 17行是前置處理，其中如果 word1 的字元如果全部沒有出現在 word2，那就直接結束回傳 0(第13行)。相似的，word2 的字元全部沒出現在 word1 中也是一樣(第17行)。第20 ~ 29行是做LCS，我們採用滾動陣列的方式，由前一列 d 算到目前列 p。
時間複雜度方面，前置處理是$O(n)$，而LCS是$O(n^2)$。
```python=
class Solution:
# lcs or word1 and reverse(word2)
# to avoid ans entirely in one string
# using direct lcs
def longestPalindrome(self, word1: str, word2: str) -> int:
n1,n2 = len(word1),len(word2)
#remove impossible head of w1 and tail of w2
#ensure the answer will match at least one of each string
w1,w2 = set(word1),set(word2)
i = 0
while i<n1 and word1[i] not in w2:
i += 1
if i==n1: return 0
j = n2-1
while j>=0 and word2[j] not in w1:
j -= 1
if j<0: return 0
word = word1[i:] + word2[:j+1]
# find lcs of word and rev(word)
n = len(word)
d,p = [0]*(n+1),[0]*(n+1) # last 0 is sentinel
longest = 0
for c in word[::-1]:
for j in range(n):
if c == word[j]:
p[j] = d[j-1]+1
else: p[j] = max(d[j],p[j-1])
d,p = p,d
return d[n-1]
```
這個程式在LeetCode上繳交的結果雖然是通過，但速度排行只在50%左右，顯示應該有更好的作法。事實上，因為Palindrome是對稱的，所以拿整條字串與它的反轉來做LCS是多做了一倍的時間。
我們可以優化這個做法，根據LCS DP的概念直接寫出在一個字串中找**最長迴文子序列**的遞迴式，而不要透過LCS來做。
For $i<j$, let $dp(i,j)$ be the length of longest palindrome subsequence of $s[:i+1]+s[j:]$. Then, $dp(i,j)=dp(i-1,j+1)+2$ if $s[i] == s[j]$; and otherwise $dp(i,j)=max(dp(i-1,j),dp(i,j+1))$.
我們由上而下，由右而左計算，也就是從兩邊往中間算。以下是範例程式，我們還是採取滾動陣列的方式。要留意的是迴文有奇數與偶數，所以在計算第 $i$ 列時，算到最後$dp(i,i+2)+1$是以$i+1$為中心的長度(第28 ~ 29行)，偶數長度的就是$dp(i,i+1)$，如第30行。
這個程式比前一支快了將近一倍，因為DP計算的格子數約是$n^2/2$。
```python=
class Solution:
# lcs or word1 and reverse(word2)
# to avoid ans entirely in one string
def longestPalindrome(self, word1: str, word2: str) -> int:
n1,n2 = len(word1),len(word2)
#remove impossible head of w1 and tail of w2
#ensure the answer will match at least one of each string
w1,w2 = set(word1),set(word2)
i = 0
while i<n1 and word1[i] not in w2:
i += 1
if i==n1: return 0
j = n2-1
while j>=0 and word2[j] not in w1:
j -= 1
if j<0: return 0
word = word1[i:] + word2[:j+1]
#print(word)
n = len(word)
d,p = [0]*n,[0]*n
longest = 0
for i in range(n-1):
p[n-1] = 2 if word[i]==word[n-1] else d[n-1]
for j in range(n-2,i,-1):
if word[i] == word[j]:
p[j] = d[j+1]+2
else: p[j] = max(d[j],p[j+1])
if i+2<n and p[i+2]+1>longest: #odd case
longest = p[i+2]+1
longest =max(longest,p[i+1]) #even case
d,p = p,d
#print(i,word[i],d,longest)
return longest
```
## Trie
Trie是一種資料結構，基本上是用來搜尋某一個字串是否在多個字串中。網路可以找到很多教學文件，例如[Geeks Trie](https://www.geeksforgeeks.org/trie-insert-and-search/)這一篇。下圖是該文件所舉的例子
Trie基本上就是個分類樹(或者說決策樹)，以這個樹狀圖來說，它儲存了四個字串，第一個字母是a的分一類，而第一個字母是d分在另外一類，同樣是a的又以第二個字母分類，....。
搜尋時，從root根據每一個字母往下走，如果中間無路可走就是找不到，如果停在某個字串的終端位置則就知道找到了某個字串，因此，在每個節點通常會存有它是否是某個字串終點的資料。
實作方面，用Python是相當容易的，標準的做法是用class，請參考上述教學文件。解題時，往往也可以用更簡單的做法，只要用一個字典來當節點就可以了，當然每個節點或者需要加上一個變數表示字串結尾。
先看LeetCode上的裸題。
[(題目連結) 208. Implement Trie (Prefix Tree) (Medium)](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)
題目就是要實作一個Trie的資料結構。必須依照題目的需求建構一個資料結構，提供四個功能，除了基本的初始化、insert、search之外，還有一個是搜尋是否有字串具有某個prefix。
以下範例程式就是個規規矩矩的寫法。我們先建構另外一個提供節點的class Node，每個節點中有兩個資料
* wordend 是儲存該節點是否是某個字串結尾的Boolean
* child 就是它的孩子的節點。本題字串限由26個字母組成，所以這裡用一個長度26的list。如果偷懶的時候就用一個字典就可以。
接著是題目要求的class Trie。
初始化很簡單，就建構一個root就可以了。insert()與search()其實很像，基本上就是由root往下走，insert()差別在於碰到不存在時，要新建節點。prefix search與search也是非常類似，只差別在prefix不一定要停在字串結尾的節點。
時間複雜度方面，Trie的新增與搜尋都是linear time。
```python=
class Node:
def __init__(self):
self.wordend = False
self.child = [None]*26 #'a'~'z'
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
p = self.root
for c in word:
k = ord(c)-0x61
if not p.child[k]:
p.child[k] = Node()
p = p.child[k]
p.wordend =True
def search(self, word: str) -> bool:
p = self.root
for c in word:
k = ord(c)-0x61
if not p.child[k]: return False
p = p.child[k]
return p.wordend
def startsWith(self, prefix: str) -> bool:
p = self.root
for c in prefix:
k = ord(c)-0x61
if not p.child[k]: return False
p = p.child[k]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
```
[(題目連結) 745. Prefix and Suffix Search (Hard)](https://leetcode.com/problems/prefix-and-suffix-search/)
題目要求建構一個class，初始時給你一堆字串；查詢時給你兩個字串 $pref$ 與 $suff$，要找出初始的字串中有無以 $pref$ 為prefix而且以 $suff$ 為suffix的字串。如果有，傳回該字串的index，如果有多個，傳回較大者，如果不存在，回傳-1。
初始的字串數量可能達到10000，但注意到每個字串長度都不超過7。
我們建構一個Trie來做搜尋，如果只查prefix或只查suffix都很簡單，但是每次查詢要滿足兩個條件就比較麻煩。因為每次會提供一對$(pref, suff)$來查詢，如果 $suff$ 的長度是固定的 $c$，我們可以把每個字串$word$改成$word[-c:]+word$插入到Trie中，也就是把字尾的 $c$ 個字母加在前面，搜尋時就搜尋 $suff+pref$。
但是查詢時這一對字串的長度並不一定。
解決的方法是：所有可能的suffix長度通通做。反正字串的長度不超過7。以下是範例程式。
這裡我們用的是偷懶方式，用字典來當節點，為了免除key值不存在的麻煩，用defaultdict最合適，根據我們的需要，我們定義 \_trie()，它簡單傳回defaultdict(\_trie)，這是根據defaultdict的要求，必須提供一個預設的函數。
第3行的WEIGHT只是要在字典中直接放一個節點的值，所以定義一個字典中不會出現的key值都可以。
初始時先建立一個root，這個root是8個節點的list，第 $i$ 個節點對應到suffix長度為 $i$ 的情形，$i=0$ 空著沒用。接著做insert的動作，第10行的迴圈會對某一個可能的長度 $i$，我們將$word[-i:]+word$新增到Trie中，並且一路將經過的節點 $v$ 的 $v[WEIGHT]$ 設為此字串的index $w$。由於我們的index是由小到大，所以最後每一個節點留下來的WEIGHT紀錄是經過它的最大index。
搜尋時就先根據查詢的 $suff$ 長度決定搜哪一棵樹。
時間複雜度與空間複雜度是$O(L^2n)$，其中$L$是字串長度，而$n$是字串數量，查詢的時間複雜度是線性時間。
```python=
def _trie():
return defaultdict(_trie)
WEIGHT = False
class WordFilter:
# suffix of possible length + prefix
def __init__(self, words: List[str]):
self.root = [_trie() for i in range(8)]
for w,word in enumerate(words): # idx as weight, always increasing
for i in range(1,len(word)+1):
v = self.root[i]
for ch in word[-i:]+word:
v = v[ch]
v[WEIGHT] = w
def f(self, pref: str, suff: str) -> int:
v = self.root[len(suff)]
for ch in suff+pref:
if ch not in v:
return -1
v = v[ch]
return v[WEIGHT]
# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)
```
以下也是一個實作所要求的class問題，LeetCode這種實作class的題目其實是為了考on-line query的題型。
[(題目連結) 1032. Stream of Characters (Hard)](https://leetcode.com/problems/stream-of-characters/)
題目是說先給你一些字串 $words$，你可以做一些前置處理。接著有一個一個的字元進入，每一個字元進入時，請檢查目前進入字元的suffix是否是 $words$ 裡面的某一個字串。
我們將$words$的字串每一個反轉後放入一個Trie中，並且將字串的最大長度與以記錄。準備一個deque來存放進入的字元。
每當一個字元進入時，我們沿著deque內的字元在Trie中進行搜尋，看看能否經過某個字串的結束節點。同時，deque的長度若超過字串的最大長度，就把多餘的pop掉。
以下是範例程式。這一題的Trie我們用一個dict就可以(第4行)。第5行$wsize$紀錄最大長度。接著將每一個字串的反轉insert到Trie中(第6 ~ 12行)，留意到第12行在一個字串的結束節點上，我們用
v['#'] = True
來表示。第14行$stream$是準備放字元的deque。
在查詢方面，字元進入時先放入$stream$的左邊，如果長度大於最大長度，就將最右邊(最早進入)的刪除。接著進入Trie的查詢，從root依照$stream$內容往下走，如無路可走，則是False，如果經過一個字串的結尾，則是True，如果全部走完也是False。
時間複雜度方面，建構花的時間是字串長度總和，查詢是字串長度的線性時間。
```python=
class StreamChecker:
#Trie of reversed words
def __init__(self, words: List[str]):
self.trie = dict()
self.wsize = max(len(w) for w in words)
for w in words:
v = self.trie
for ch in w[::-1]:
if ch not in v:
v[ch] = dict()
v = v[ch]
v['#'] = True
#end for
self.stream = deque()
def query(self, letter: str) -> bool:
self.stream.appendleft(letter)
if len(self.stream)>self.wsize: self.stream.pop()
v = self.trie
for ch in self.stream:
if ch not in v: return False
v = v[ch]
if '#' in v: return True
return False
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)
```
## Rolling hash
字串題常用到Hash，Hash通常翻譯為**雜湊**，Hash的主要觀念是用一個函數將字串對應到一個整數，不同的字串盡可能不會對應到相同數字，這樣查詢字串時可以查詢它對應的數字，因為有可能兩個不同字串對應到相同數字(稱為Hash collision)，所以可能發生False positive (偽陽性)，也就是查詢找到對應的數字但並非要找的字串，但只要碰撞的機率很小，那麼平均查詢的時間還是會很少。Hash 背後牽涉的數學與技術非常複雜，應用也廣泛，這裡就無法多談了。
**Rolling hash**是Hash的一種形式，可以在網路上找到很多介紹，例如 [Wiki](https://en.wikipedia.org/wiki/Rolling_hash)。主要想法是把字串看成一個多項式，每一個字元是多項式的一項係數，例如，我們以a->0, b->1, ...把字元轉換為數字，取$x=31$，字串'abcde'就對應到
$$
\begin{array}{ll}
&&0\cdot x^4+1\cdot x^3+ 2\cdot x^2 + 3\cdot x + 4 \\
&=& 0+29791+2\cdot 961 + 3\cdot 31 + 4 \\
&=& 31810
\end{array}
$$
項次由高到低或由低到高都可以，使用時定義一致即可。
所謂滾動(捲動)之意是當這個字串右邊加一個左邊減一個的時候，我們可以很快的算出新的Hash 值，例如'abcde' -> 'bcdef'，那麼我們將原來的值減去最左邊一項的$0\cdot x^4$，然後將剩下的值乘以$x$(左移一項)，在加上新的最右邊一項，就可以得到，也就是
$h(\text{bcdef}) = (h(\text{abcde}) - 0\cdot x^4)\times x + 5$
這個移動的情形，常出現在一個長字串中歷遍每一個固定長度的substring。由於這個對應的數字只要字串稍長就會很大，所以通常都會以一個大質數(例如$10^9+7$)取模(modulo)。
這個方法稱為Rolling hash，使用Rolling hash來做string maching的演算法也稱為Rabin-Karp algorithm。
下面這一題是我們在前面介紹KMP時看過的題目，它其實也可以用Rolling hash來解。LeetCode比較不強調要記得很多演算法，而是會運用演算法的觀念來解題目，所以很多問題都有不同的解，字串問題常常會有Hash的解法。
[1392. Longest Happy Prefix](https://leetcode.com/problems/longest-happy-prefix/) 的另外解法。
題目是說給你一個字串 $s$，要找出(除了$s$自己之外)最長的一段前綴(prefix)，該前綴也是 $s$ 的後綴(suffix)，也就是說，若 $s$ 的長度為 $n$，要找出最大的 $k<n$，滿足$s[:k]==s[-k:]$。前面提到過這題其實是KMP算法的核心所在，利用實作KMP可以很有效率的解本題。
這裡提出一個不使用KMP，只根據hash的精神來做的方法。
既然要找前綴等於後綴，我們就將所有前綴與後綴的rolling hash算出來，相同長度的予以比較其hash value，因為會有False positive，所以我們處理的方法是：當hash value相同時，我們記錄在一個list中，比對終了後，我們把list中由長到短的來做字串的實際比對。
我們來看看這麼做的好處。假設我們直接做字串的比對，長度 $i$ 的要花費$O(i)$的時間，不管你由長到短還是由短到長，worst case會跑到$O(n^2)$，例如字串'aaaaa....'。
至於Rolling hash的做法，長度每增加1，更改hash value只需要$O(1)$，hash value的比對也是$O(1)$，所有比對完畢只花費$O(n)$。接下來要處理偽陽性的檢查，但因為發生機率很低，所以非常大的機率只會做1 ~ 2次。
請留意幾件事。
* 由短到長計算rolling hash並比對成功時，為何不直接recheck，而是暫時放入一個list，最後才由長到短recheck？因為可能會花費太多實際比對字串的時間。
* 本題也可以從長到短的計算並比對rolling hash，速度會快一點。
```python=
class Solution:
# rolling hash, small to large
def longestPrefix(self, s: str) -> str:
mod = 1000000009
cand = []
x = 26
xn = 1
prefix = suffix = 0
for i in range(len(s)-1):
prefix = (prefix+ord(s[i])*xn)%mod
xn = xn*x%mod
suffix = (suffix*x+ord(s[-i-1]))%mod
if prefix==suffix:
cand.append(i+1)
# recheck
while cand:
leng = cand.pop()
if s[:leng] == s[-leng:]: return s[:leng]
return ""
```
**注意事項：**
在LeetCode很常看到有些人的解，在使用hash後不處理collision的狀況，只要質數取得夠大，碰撞的機率就極小，可以通過測資就不管了。這種想法筆者覺得真是大不以為然，程式比賽可以測資過了就算了，你如果去面試或是去做事，怎麼可以測資過了就算了，你得講得出你的方法為什麼會對，不能為了程式短一點，跑得快一點，就冒著錯誤的風險。使用程式語言提供的hash時，它會處裡collision，如果是自己做，例如rolling hash，就必須自己處理。
[(題目連結) 214. Shortest Palindrome (Hard)](https://leetcode.com/problems/shortest-palindrome/)
題目是要你在一個字串 $s$ 之前加上最少的字元，使它變成一個palindrome。
稍微想一下，如果要加入的最短字串是$w$，也就是說$w+s$是個迴文，那麼$w$必然是$s$某個後綴的反轉，也就是說$w+s = w + p + rev(w)$ 而且 $p$ 是一個迴文。例如$s$ = 'abcbade'，那麼$w$ = 'ed'，而$p$ = 'abcba'。
所以，本題就是在找最長的prefix palindrome。
以下是使用暴力法的程式，由長而短枚舉前綴，檢查是否是迴文，時間複雜度是$O(n^2)$。
```python=
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
for i in range(n,0,-1): # length i
if s[:i] == s[i-1::-1] :
return s[n-1:i-1:-1]+s
# always true for i=1
return "" # when s = ""
```
有點驚訝這個這麼簡單的暴力程式可以通過，但 Runtime rank = 33\%不是太好。我們用Rolling hash來做一些協助。以下是範例程式。
我們一樣由前往後檢查長度為 $i$ 的prefix，計算出它與它的反轉字串的rolling hash，如果兩個值相等，就放入一個list中當作是可能的解，最後我們有長到短實際檢查這些可能的解。這個程式大機率可以在線性時間跑完。實際執行要比前一支程式快了很多倍。
```python=
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
cand = [] # candidate
hash1 = hash2 = 0 # hash of s[:i] and its rev
mod = 10**9+7
x = 29; xn = 1 # x power
for i in range(n): # s[:i+1]
hash1 = (hash1*x + ord(s[i])-0x61)%mod
hash2 = (hash2 + (ord(s[i])-0x61)*xn)%mod
if hash1 == hash2: cand.append(i)
xn = xn*x%mod
#
for i in cand[::-1]:
if s[:i+1] == s[i::-1]:
return s[n-1:i:-1]+s
return "" # for s = "" empty
```
[(題目連結) 1044. Longest Duplicate Substring (Hard)](https://leetcode.com/problems/longest-duplicate-substring/description/)
題目很簡單，就是在一個字串中找出重複出現(兩次或更多次)的最長子字串。
對於給定長度，我們可以用rolling hash來幫忙找出重複出現的子字串，大機率下只花$O(n)$。問題是我們不知道長度。
因為如果有長度為$k$的重複字串，則一定有長度$k-1$的重複字串，所以重複字串的長度具備單調性，解決之道是二分搜長度。
以下是範例程式。第7 ~ 20行的函數check() 是找給定長度$leng$時的重複字串，如果沒有重複字串就回傳-1，否則回傳出現的位置。其中，我們還是寫了萬一碰撞時的檢查機制。
第22 ~ 31行是二分搜長度，這裡要搜的長度保持在$[low, up)$的左閉右開半區間。寫二分搜要留意自己的定義才不會寫錯。
時間複雜度方面，每次檢查是$O(n)$，會檢查$O(\log n)$次，所以在大機率之下整體複雜度是$O(n\log n)$。
```python=
class Solution:
#binary search the length and using rolling hash
def longestDupSubstring(self, s: str) -> str:
num = [ord(c)-0x61 for c in s]
mod = 1000000007
base = 29
def check(leng):
px = pow(base,leng,mod) # (26**leng)%mod
code = 0
dic = defaultdict(list)
for i in range(leng):
code = (code*base+num[i])%mod
dic[code].append(0)
for i,p in enumerate(num[leng:], start = leng):
code = (code*base-num[i-leng]*px+p)%mod
for pos in dic[code]:
if s[pos:pos+leng] == s[i-leng+1:i+1]:
return pos
dic[code].append(i-leng+1)
return -1
# main, binary search
low,up = 0,len(s) # [low,up)
start = -1
while up-low > 1:
mid = (low+up)//2
i = check(mid)
if i >= 0:
start = i
low = mid
else: up = mid
# end while
if start < 0: return ""
return s[start:start+low]
```
最後看一題有點趣味的題目。
[(題目連結) 1316. Distinct Echo Substrings (Hard)](https://leetcode.com/problems/distinct-echo-substrings/)
題目要是在一個字串中找出所有相異的**Echo substring**，所謂echo string是指一個字串$s = t+t$，也就是前半段與後半段相等，例如 'abab'與 'aabaab'。
我們運用rolling hash的方式將字串對應成多項式的值，以字串左端為低冪次，若
$h(i) = s[0]+s[1]\cdot x+s[2]\cdot x^2+\ldots+s[i]\cdot x^i$，那麼我們可以很快算出
$s[i:j+1]$的多項式值為$h(j)-h(i-1)$，而$s[j+1:k+1]$的多項式值為$h(k)-h(j)$，若兩者長度相等時，$k=2j+1-i$，此時若兩字串相等他們的多項式值剛好是移動了$j+1-i$項，也就是
$(h(j)-h(i-1))\times x^{j+1-i} == h(k)-h(j)$。
我們可以利用這個方式來判斷給定長度的echo string。本題需要找各種長度，以下是範例程式。
第6 ~ 8行先算好$x^i$，這裡我們取$x=26$。接著第9 ~ 11行算$h(i)$，為了方便前面放了一個$h[0]=0$，所以程式中的項次會往後移一位。第12行的$ans$是個用來放答案的集合，本題要求找出不一樣的字串，所以相同字串只留一個。
第13行的迴圈每次找位置$i$開頭的，內迴圈$j$則是跑各種區間$[i,j]$，我們要檢測是否$text[i:j+1]==text[j+1:k+1]$，其中$k=2j-i+1$，也就是前後兩段等長。第17行算出移項後兩段的hash value差值，第18行若hash value相等且字串相同即放入答案中。
請注意這麼寫看似與直接暴力法一樣，甚至多此一舉，第18行直接比字串就好，根本無需計算比hash value的$d$值，事實上是不一樣的，因為if 的邏輯判斷式有short-circuit evaluation，除非 $d\%mod == 0$，否則是不會去比較字串的，也就是hash是用來減少比較字串的次數。
時間複雜度方面，worst case是蠻糟糕的$O(n^3)$，跟暴力法一樣，但是大機率的是$O(n^2)$，只有在輸入字串類似於一個重複字串，$text = s+s+s+s\ldots$的時候，所有長度是$2len(s)$的倍數的子字串都是答案，才會跑到$O(n^3)$。LeetCode上的測資是可以通過的。
```python=
class Solution:
# square string, rolling hash
def distinctEchoSubstrings(self, text: str) -> int:
n = len(text)
mod = 1000000009
power = [1] #26^i
for i in range(n-1):
power.append(power[-1]*26%mod)
h = [0] # dummy head, polynomial hash
for i,c in enumerate(text):
h.append((h[-1]+(ord(c)-0x61)*power[i])%mod)
ans = set()
for i in range(n): # start at i
for j in range(i,n): # if [i,j] == [j+1,k]
k = j+j+1-i
if k>=n: break
d = (h[j+1]-h[i])*power[j+1-i] - (h[k+1]-h[j+1])
if d%mod == 0 and text[i:j+1]==text[j+1:k+1]:
ans.add(text[i:k+1])
#print(ans)
return len(ans)
```
如果我們仔細想一想，其實這題根本就不必使用hash。我們如果要找指定長度$leng+leng$的echo substring，我們可以歷遍整個字串，檢查第$i$個字母$text[i]$是否與$text[i-leng]$相同，只要有連續$leng$個相同，就是找到一個答案的字串。
以下是範例程式，我們用$nsame$來記錄目前有幾個連續相同。時間複雜度是一樣的，雖然看似$O(n^2)$，但最壞的重複字串還是可能跑到$O(n^3)$，因為這支程式雖然沒有做字串比對，但是在加入答案時(第12行)，對每個答案還是要花該字串長度的時間。不過這個程式對LeetCode的測資已經相當快了，筆者繳交測試時的rank已經是94\%。
```python=
class Solution:
# square string, no hash
def distinctEchoSubstrings(self, text: str) -> int:
n = len(text)
ans = set()
for leng in range(1,n//2+1): # length leng+leng
nsame = 0 # num of consecutive same
for i in range(leng,n): # right start at i
if text[i] == text[i-leng]:
nsame += 1
if nsame >= leng:
ans.add(text[i-leng-leng+1:i])
else:
nsame = 0
return len(ans)
```
我們可否再優化改善上述重複字串的狀況呢？答案是可以的，我們在將$i$結尾的字串放入答案之前，檢查一下$i-leng$是否也是長度$leng+leng$的echo substring，如果是，這兩個字串必為相同字串，就不必加入。以下是修改後的範例程式。
對於每一個長度，我們用一個集合$idx$放所有答案的結尾index，第13行多做一個檢查才加入$ans$，第15行維護好$idx$。
這個程式比前一個快一些，但也不會差太多，時間rank 約98\%。Worst case時間複雜度有無改善呢？或者只是某些字串也改善？筆者初步看起來可能big-O是有改善，但不容易證明。
```python=
class Solution:
# square string, no hash
def distinctEchoSubstrings(self, text: str) -> int:
n = len(text)
ans = set()
for leng in range(1,n//2+1): # length leng+leng
nsame = 0 # num of consecutive same
idx = set() # index of candidate
for i in range(leng,n): # right start at i
if text[i] == text[i-leng]:
nsame += 1
if nsame >= leng:
if i-leng not in idx:
ans.add(text[i-leng-leng+1:i])
idx.add(i)
else:
nsame = 0
return len(ans)
```
## 結語
字串問題很多樣，有些只是一種出題方式，算法上還是與一般數列問題相同，但有些問題則是用到某些長久以來發展出來的特殊算法。LeetCode比較強調算法觀念的運用而非特殊算法的知識，所以字串問題很多會運用hash，這些方法的重點有時是在大機率下的程式效率而非單指worst case的時間複雜度，使用hash時還是應該考量collision的處理，在worst case時可以承擔程式跑得比較慢，而不是要承擔程式得到錯誤的答案。
Sign in with Wallet
Connect another wallet