字元串匹配算法
KMP(Knuth-Morris-Pratt)算法是一種高效的字元串匹配算法。
這種算法能夠在大量文本中快速查找特定的子串，它的核心思想是利用已經匹配過的信息來減少不必要的字元比較次數，從而提高匹配效率。KMP算法由Donald Knuth、James H. Morris和Vaughan Pratt於1977年共同提出，因此得名克努特—莫里斯—普拉特操作。
這種算法通過計算模式串的最長公共前後綴（即前綴和後綴相同的最長部分），來確定當模式串與文本串不匹配時，下一步應該將模式串向右移動多少位。這樣，KMP算法可以在每個不匹配的情況下跳過儘可能多的字元，而不是像樸素匹配算法那樣每次只將模式串右移一格。這種最佳化顯著減少了比較次數，提高了搜尋效率。