The KMP algorithm is a powerful string matching technique developed by Knuth, Morris, and Pratt. Unlike naive string matching that may require backtracking in the text, KMP uses preprocessing to avoid redundant comparisons. Here we see a text string and a pattern we want to find within it.
The failure function, also called the next array, is crucial for KMP's efficiency. For each position in the pattern, it stores the length of the longest proper prefix that is also a suffix. For example, in pattern ABABA, at position 4, the value is 3 because ABA appears at both the beginning and end of the substring ABABA.
Here we see the KMP matching process in action. When comparing the text and pattern, we encounter a mismatch at position 4. Instead of moving the pattern just one position, KMP uses the next array value to shift the pattern efficiently. The next value of 2 tells us we can skip ahead, avoiding redundant comparisons.
KMP算法是计算机科学中一个重要的字符串匹配算法。它由三位科学家Knuth、Morris和Pratt共同提出，用于在文本中高效地查找模式串。与朴素的字符串匹配算法相比，KMP算法能够避免不必要的回溯，从而大大提高匹配效率。
朴素的字符串匹配算法效率很低。当模式串与文本串不匹配时，算法会将模式串向右移动一位，重新开始比较。这样会导致大量重复的比较操作，特别是在有很多重复字符的情况下，时间复杂度可能达到O(nm)，其中n是文本长度，m是模式串长度。
KMP算法的核心是构建一个叫做"失败函数"或"Next数组"的数据结构。这个数组记录了模式串中每个位置的最长相同前缀后缀的长度。当字符匹配失败时，我们可以利用这个信息，直接跳到下一个可能匹配的位置，而不需要从头开始比较。这样就避免了不必要的回溯，将时间复杂度降低到O(n+m)。
这是KMP算法的核心实现。函数接收文本和模式串作为输入，首先构建失败函数，然后进行匹配。当字符匹配时，两个指针都向前移动；当字符不匹配时，我们使用Next数组来高效地跳过位置。这个算法实现了线性时间复杂度O(n+m)，比朴素算法效率高得多。