記錄學習內容。看網路上大大們的文章和影片，做些紀錄。
以下內容大多來自網路上大大們的文章。截圖也來自文章和影片。
還不了解，內容可能有錯誤。

9.2 Rabin-Karp String Matching Algorithm
https://www.youtube.com/watch?v=qQ8vS2btsxI&ab_channel=AbdulBari

Rabin-Karp Algorithm for Pattern Searching
https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/

問題:

字串 : "AABAACAADAABAABA"
pattern : AABA
找出 字串 哪裡有pattern ?

不太懂，方法是說
每個字母 代表 一個數字 。
像是 A --- >0 ， B --- >1 ， C-- >2

所以 AABA 會變成 0 +0 + 1+0 = 1
AABA = 1 稱為 hash value
然後在原本的"AABAACAADAABAABA"
只要有4個字母相加等於1 。就代表有這個pattern 。

但這會有個問題 ， 4個字母相加等於1 ，會有很多種情況:

0 +0 + 1+0 = 1
1 +0 + 0+0 = 1
0 +1+ 0+0 = 1
0 +0 +0+1 = 1

所以這個演算法的缺點就是 ， 如果你選的數字 ，一直重複，還是要再檢查很多字母。

判斷完4個字母相加 是1 以後 ，你還要再檢查一次4個字母是不是一樣。

AABA = 1
ABAA = 1
AABA = 1
AAAB = 1

最好的時間 就是 (n-m+1) --- >時間複雜度O(n-m+1)
最慢的時間 (n-m+1)*m --- >時間複雜度 O(nm)

最好的時間應該 改成 O(n+m)
n 代表 n-m+1  
m (pattern 長度)代表 pattern 製作 hash value

最慢的時間 ，乘3 是因為 每次都要再檢查一次pattern 。

如圖:

所以要盡量讓數字變得越怪越好 。這樣才會比較唯一 。

方法是這樣:

如果 A =1 ，B=2 ,C=3
字串 : "AABAACAADAABAABA"
pattern : AABA

AABA 變得像 (數字表示的方法)

1 * 3的3次方 +  1 * 3的2次方  +  2 * 3的1次方 + 1 * 3的0次方
= 9+ 9 +6 +1 =25 
這樣比較不會重複 。

但是 可能會數字太大 ，可能會超過數字限制?
所以會在後面 除 一個質數 ，取餘數

看一下這段:
印出來的hash code 長這樣:
//71 ，65，44，27

最後p和 t相同 ，就代表hash value 一樣 ，就是正確答案。
(還不懂)

最後一段:
因為不符合pattern ，所以 去掉最左邊 ，補上右邊一格，繼續看下一段符不符合pattern。

看不懂程式，先了解到這。

接下來看KMP

9.1 Knuth-Morris-Pratt KMP String Matching Algorithm
https://www.youtube.com/watch?v=V5-7GzOfADQ&ab_channel=AbdulBari