重念一次早該補起來的「資料結構與演算法」。這篇筆記下 KMP 字串尋找的程式碼。
課程相關資訊
[連結]:https://hiskio.com/courses/572/lectures/30001
本篇範圍:Chapter 12
請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。
內容
1. i 和 j 代表 str1 和 str2 從頭開始的 index
2. counter 代表在 str1 內出現多少個 str2
3. 當 j 的長度跟 str2 一樣時,可以將 j 設定為 str2 的 lps [j-1] 項,以避免重複比較