給一字串 S，要找出最大的重複連續字串，重複字串可部分重壘。
參考︰力扣
在這題出的這天，感覺最近要開始爆忙，也在想要不要先斷一下寫題解？但這題有難度，還是想把它做掉。
這題要用到「Rabin-Karp 's algorithm」，用來字串搜查，使用方法是把子字串做Hash轉換去對比。
但我從頭開始講，為什麼得用 Rabin-Karp 's algorithm ？
要從一字串內找的重複出現子字串時，會使用 suffix Array，中文是後綴表。
suffix Array
例一：
banana，生成後綴表 => [banana, anana, nana, ana, na, a]
然後依字母大小跟長度排序 => [a, ana, anana, na, nana, banana]
拿 [i] [i+1] 去找前綴最長共同長度 => a,ana: 1, ana,anana:3 ,...
共同前綴最長部分就是題目所求，也就是取最大值。
為什麼可行？在排序的時候，就已經把性質相近，組成相似的排在一起，因此只會跟最有可能有最長共同前綴的相比。
這方法的時間複雜度很大，因此需要改良。
提示一：Binary Search。
例二：
banana 的長度為 6，因此最大重複字串的長度不會超過五，會落在[0,5]間，從中間先找長度 3 有沒有出現重複子字串，
這會比起例一每次都從長度 1 開始，還快上不少。
比較的參照是用 HashSet，取二分法的長度 m，從頭把長度 m 的子字串輪一遍，先檢查是否在 HashSet，若有就是有重複出現，沒有就把放入HashSet。
因此 banana 會從長度 3 開始，有，l = 4。接著 m = (6-4)//2+4 = 5，拿長度 5 找，沒有，r = 5。
最後 m = 4，沒有，r = 4，此時 l < r == False，結束。因此可知最大的長度為 4-1 => 3。
找到重複時，就可以回傳其對應到的位置，也不用繼續找 下去。
但是，數量一大，子字串是 string，長度相對也會爆炸式增長，這使得記憶體會巨大消耗，會超使用限制。
提示二：Rabin-Karp 's algorithm。
用簡單來講，就是把字串的位置跟值做 hash，然後得到一個能表示字串組合的hash值，該值若有在HashSet，就代表有重複。
把可能出現的值給一個對應值，這題只有英文小寫字母，故會有26個值，從 0 到 25 。
如果長度為2為下，hash值為0，那可對應 aa。hash值26，為ba。
例二的最大問題是「記憶體使用太多」，如果把子字串資訊轉換成hash值，hash值不超過 log2(26*26)，
也就是佔用不超過10bit，但長度為2的string，至少也16bit。因此可以有效解決記憶體使用太多的問題。
雖然目前的hash值保證為1對1，但如果這樣算，一旦長度為32以上，hash值可能有超過26**32，這值太大會在某些語言造成溢位出現。
把值對一個大數取餘，就能限制hash值的長度，也會有開始有多值對一個hash的可能，但大數夠大，發生的機率是相當的低。(大部分的hash都會去限制長度，如：MD5、SHA256)
我不是很喜歡這題，因為正確的寫法可能會過不了。
class Solution:
def longestDupSubstring(self, S: str) -> str:
hashMap = dict()
count = 0
nums = []
for c in S:
if c not in hashMap:
hashMap[c] = count
count += 1
nums.append(hashMap[c])
mod = 2**64
def search(length):
SubStrHash = 0
for i in range(length):
SubStrHash = (SubStrHash*count + nums[i])%mod
hashset = {SubStrHash}
al = (count**length)%mod
for i in range(length, n):
SubStrHash = (SubStrHash*count - nums[i-length]*al + nums[i])%mod
if SubStrHash in hashset:
return i
hashset.add(SubStrHash)
return -1
n = len(S)
l, r = 0, n
end = -1
while r > l:
m = (r - l)//2 + l
res = search(m+1)
if res == -1:
r = m
else:
l = m + 1
end = res
return "" if end == -1 else S[end - r + 1: end+1]