KMP

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris于1977年联合发表。它通过预处理模式串，构造一个“部分匹配表”，记录模式串中每个前缀的最长相等真前缀和最长相等真后缀的长度。在匹配过程中，当主串与模式串不匹配时，利用部分匹配表可以直接将模式串向右移动至下一个可能的匹配位置，避免了从头开始的繁琐比较。这使得KMP算法的时间复杂度仅为O(n+m)，其中n为主串长度，m为模式串长度。KMP算法广泛应用于文本搜索、数据压缩等领域，被认为是字符串匹配领域的里程碑式成果。