KMP算法详解：避免回溯的高效字符串匹配

KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三位学者提出，旨在解决在一个字符串（主串A）中查找另一个字符串（模式串B）是否存在，以及存在时的位置问题。相比于朴素的字符串匹配算法，KMP算法避免了不必要的回溯，从而提高了效率。 在KMP算法中，关键的概念是next值，也称为部分匹配表。这个表定义了模式串中每个位置的最长公共前后缀。例如，模式串 "a b a a b c a c" 的next值序列为 "0 1 1 2 2 3 1 2"。next值的计算方法是：第一个字符的next值为0，第二个字符的next值为1。对于后续字符，如果它与前一个字符相同，那么其next值等于前一个字符的next值加1；如果不相同，就向左移动，比较当前字符与它的next值所对应的字符，直到找到相等的字符或移动到第一位，然后使用找到的相等字符的位置作为next值。若找不到相等字符，next值为1。 在KMP算法执行过程中，有两个指针i和j。i指向主串A的当前位置，j指向模式串B的当前位置。当A[i]等于B[j]时，i和j都向右移动；若A[i]不等于B[j]，但B[j]之前有匹配的部分，即B[j - next[j]]等于A[i - 1]，则j会回退到next[j]，而i保持不变。这样可以避免重新比较已知匹配的部分，减少了比较次数，提升了效率。 举例来说，对于A="abababaababacb"和B="ababacb"，在i=5，j=5时，A[i]和B[j]不匹配。因为next[5]是3，所以j会回退到3，此时B[3]与A[5-3+1=3]相等，于是i和j继续前进。当j到达模式串末尾，即j=m时，说明找到了匹配的子串，并可以根据i的值确定匹配位置。 KMP算法的时间复杂度在最坏情况下为O(n)，其中n是主串A的长度。由于KMP算法避免了重复比较，它在大多数实际应用中表现优秀，尤其在处理长字符串时，效率远超朴素的字符串匹配算法。