重念一次早該補起來的「資料結構與演算法」。這篇筆記下 KMP 字串尋找。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29996
本篇範圍：Chapter 12
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 以人腦的方式來在字串中找 substring，你會使要跳躍式的找法。如果你的 pattern 有部分符合的話，你會找相似的內容才去做比對
2. LPS ( Longest proper prefix which is also suffix )，亦即前綴和後綴是有機會相同的，那就去看此時的相似總長度是多少
3. proper prefix 和 proper suffix 是不包含最後一個詞的
4. LPS Array 的第 0 項為字串的第一個 proper prefix 和 proper suffix 為 0，之後以此類推
