KMP算法1

KMP算法，全称Knuth-Morris-Pratt算法，是一种高效的字符串匹配算法，由Donald Knuth、Stephen Morris和Vaughan Pratt三位学者提出。它的主要目标是在一个长字符串（主串A）中查找是否存在一个短字符串（模式串B）作为其子串，而且在最坏的情况下具有线性时间复杂度O(n)，其中n为主串A的长度。相较于朴素的字符串匹配方法，KMP算法避免了不必要的字符比较和回溯，提高了效率。 在KMP算法中，关键在于构建一个“部分匹配表”（也称为“next数组”），它记录了模式串B在不匹配时如何调整位置的信息。这个表定义了当模式串的某个位置与主串不匹配时，可以将模式串的指针j回退到何处，以保持之前已匹配的部分不被破坏，同时使得新的B[j+1]能与A[i+1]匹配。 以题目给出的例子为例，A="abababaababacb"，B="ababacb"。初始时，i和j都为1，分别指向A和B的第一个字符。当i和j同步增加，且A[i]与B[j]匹配时，算法正常进行。但是，当i=6，j=5时，A[6]≠B[6]，按照KMP策略，我们需要找到一个新的j值（j'），使得B[1..j']与B[j'-j+1..j]相同，以便A[i-j'+1..i]仍与B[1..j']匹配，且A[i+1]能与B[j'+1]匹配。在这个例子中，B[1..5]与B[3..5]都为"aba"，因此j'可以是3，此时B[j'+1]即B[4]与A[i+1]匹配，所以j变为4，i不变。 部分匹配表P[j]的计算基于模式串B自身，通过观察B的前后部分是否具有相同的前缀和后缀。例如，对于B="ababacb"，P[1]=0，P[2]=1，P[3]=1，P[4]=3，P[5]=3，P[6]=0。这意味着当比较到B的第六个字符不匹配时，可以将j回退到0，重新开始匹配。 KMP算法的具体步骤如下： 1. 预处理模式串B，生成部分匹配表P。 2. 初始化i=1，j=1，分别指向主串A和模式串B的第一个字符。 3. 当i<A的长度时，执行以下操作： - 如果A[i]与B[j]匹配，则i和j都加1，继续比较下一个字符。 - 如果A[i]与B[j]不匹配，根据部分匹配表P[j]的值，将j回退到P[j]，并保持i不变。 - 重复此过程，直到找到匹配或i达到A的末尾。 KMP算法的精髓在于避免了不必要的回溯，通过部分匹配表提前知道在不匹配时应该如何调整模式串的位置，使得算法在最坏情况下仍然保持线性时间复杂度，大大提高了字符串匹配的效率。