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

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

問題:

字串: "abcdabcabcdf"
pattern : "abcdf"
找出 字串 哪裡有pattern ?

一般直接的想法 :

字串 前面有 abcda …
Pattern  abcdf 在 第 5個字母會失敗 。

可是字串已經 從 a跑到 索引4 的a 了 。
pattern  abcdf 也跑到最後一個 字母 f 了。
 
所以 失敗 後 ，
字串退到 第二個字母: b
pattern 則退到第一個字母。

字串的每一個字母 最糟糕 都要 檢查到pattern的最後一個字母

所以時間複雜度 是 字串長度 * pattern長度

教學裡的例子:

String : aaa aaa aa b
Pattern : aaab

程式執行次數 就很接近 時間複雜度: 字串長度 * pattern長度

將著講到 用 KMP String Matching Algorithm 解決這個問題:

字串 ababc abc aba babd

Pattern :
a b a b d
0 0 1 2 0

ab  是pattern 重複的地方 。 所以第二個 a b 換成數字 會變成1、2(不太懂)

然後當 字串 到第一個 c的時候 ， pattern 會失敗 。
但是pattern 不用急著回到 最前面 ， 會2-1 = 1 (1代表pattern索引)，跳到 a b a b d 中的 第一個 b 。

如果再跟字串第一個 c 比較失敗 ，才會 回到最前面 。

所以現在pattern 又到最前面了，但是字串 不用在往回跑 ，直接下一個字母。
直覺來想，就是字串中的 ababc 沒有符合pattern ，可以直接放棄abab ，從c開始

這個演算法的特色: target string(字串)不用往回跑 ， pattern 往回跑到重複的地方 。 

這個例子 ，在看一下 :
String : aaa aaa aa b
Pattern : aaab

Pattern 的 aaab 的b 會失敗 ，然後會往前面的a檢查 。發現一樣 ，所以String往下一格跑 。

可以想成 aaa 在前面都match了 ，所以不用一直往回走 。接著String會不斷地往下一個字母檢查 ，
然後pattern 就會一直 在第3個a 和b之間檢查 ，直到String 到最後一個b 。

時間複雜度 是 O(n+m) 不懂 。
因為 String 一直往下一個字母走 ，所以是 n 。
m是pattern長度 ，因為pattern的字母個數是m ，形成字母的數字陣列的時間複雜度是m。
所以是n+m

接著看:
KMP Algorithm for Pattern Searching
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
Naive algorithm for Pattern Searching
https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/

Pattern searching is an important problem in computer science. When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results.

在一個字串中 找 pattern 是很常見的功能 。
Control+F ，在網頁 、記事本 常常用到 。

先看NaiveSearch

就是字串 一個字 ，一個字 ，跟pattern 比較 。

為什麼會是N-M ， 因為

String txt = "AABAACAADAABAAABAA"; 
String pat = "AABA";
Txt 最後面的BAA可以去掉 。

接著來看 KMP的部分:

Pattern 的 數字陣列 :

文章裡有完整的步驟，很詳細 。

pattern 製作 數字陣列:

數字陣列的每一個值 ，代表 pattern (重複string) 的索引
(不清楚要這麼形容)

len 代表 pattern 裡面  重複的 string 長度 (一開始是pattern的索引0)。

如果 i (一開始是pattern的索引1)和 len 字母一樣 ，就會增加 len 長度 和  到下一個字母(i++)。

如果 i 和len 字母不一樣 ， 這時候如果len > 0 代表-- > 要去找 {pattern裡面重複的string的上一個字母} ，看有沒有符合的當前的i  (這時候 i 不用在往下一個跑 )。

如果 i 和len 不一樣 ， 這時候如果len = 0 代表 {pattern裡面重複的string} 都沒有符合i ，所以直接給 0 ， 接著到pattern的下一個char -- > i++ 。

接著來看主程式:

// i 是 text 索引  ，n是 text length

// j 是 pattern 索引  ，m 是 pattern length

如果Pattern 和 text 相等 ，就到下一個字母。

如果Pattern 和 text 不相等 :
    j 大於 0的話  ，  lps[j -1] 值 拿去 當pattern字母索引 ，繼續和當前i比較
    j 等於0的話 ，代表當前text字母 沒有和pattern符合 ， 所以前往text的下一個字母

還是不太懂，接著參考:

Knuth-Morris-Pratt (KMP) algorithm | String Matching Algorithm | Substring Search
https://www.youtube.com/watch?v=4jY57Ehc14Y&ab_channel=LogicFirst

failure function 就是前面講到的 ， 產生(pattern 的 的數字陣列) 的func

KMP算法詳解
https://medium.com/nlp-tsupei/kmp%E7%AE%97%E6%B3%95%E8%A9%B3%E8%A7%A3-1b1050a45850

KMP主要利用「次長的相同前綴後綴」來省下重複的比對過程
不知道 什麼是次長的相同前綴後綴。

教學裡的例子 :

target = "PAPCAPZ"

pattern = "APCAPK"

pattern 的AP 在索引0 和1 ， 第二個AP在索引3和4

target(目標字串)  AP  在索引 1 和 2 
 
所以 可以直接 從 pattern的索引3和4 ，檢查target的索引 1 和 2 ，不用一直回到索引0和1

KMP總結

1 加速這類問題:

String : aaa aaa aa b
Pattern : aaab

2 步驟

一
製作pattern 的char 的數字陣列 (failure_function)

時間複雜度 是 m (m變數代表pattern的長度)

二
開始 pattern 和 text 的比較 ， 找text 哪裡有 pattern 。

時間複雜度是 n ，因為text的字母 一格一格往前 (n代表text的長度)

三
全部的時間複雜度 就是 (n+m)

還是一知半解，內容可能有誤。

再稍微看一下
Rabin-Karp Algorithm
https://ithelp.ithome.com.tw/articles/10242296

Rabin-Karp Algorithm的時間複雜度 之前是這樣認為:

最好的時間 就是 (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

所以是n+m ?

之後有看教學:
花花酱 KMP Algorithm - 刷题找工作 SP19
https://www.youtube.com/watch?v=uKr9qIZMtzw&t=1321s&ab_channel=HuaHua