kmp

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris于1977年联合发明。它的核心思想是利用已知的部分匹配信息，避免在文本串中的多余比较，从而提高匹配效率。KMP算法通过构造一个前缀函数（也称为部分匹配表），记录每个子串的最长相等真前缀和后缀的长度，当发生不匹配时，可以利用这个信息直接将模式串向右移动至与文本串当前位置的最长相等前后缀对齐的位置，继续进行匹配。这使得KMP算法的时间复杂度为O(n+m)，其中n为文本串长度，m为模式串长度。