MP是由基础的字符串匹配BF算法改进而来的KMP模式匹配算法原理目标串主串 S heloohello, 模式串子串 T hello。我们要从主串 S 中找到子串 T 的位置。如果使用BF算法步骤如下图所示。在 ① 中当 S 和 T 不匹配时BF算法的操作是主串 S 回退到 i-j1从本次匹配的初始位置后移一位图中步骤②的位置匹配串 T 回退到 j 0 (初始位置, 然后执行 ②③④⑤⑥ 步依次进行匹配但所有这些步骤一定都是必需的吗在步骤 ① 中单看模式串 T前三个字符均不相等h ! e ! l同时S 和 T 串前三个字符又相匹配那么模式串 T 的首字符h 自然不可能和主串 S 的第二、三位字符相等。所以步骤②③都是多余的。这是KMP算法的关键所在如果我们知道 T 串中哪些字符相等也是关键点后续会讲那么有些步骤就可以省略。因此只需要保留①④⑤⑥的步骤即可。从下图可以看出指针 i 是不是一直没有回溯这就是KMP的妙处所在。在KMP中指针 i 永远不会回溯只有指向模式串的指针 j 会发生回溯。在本例中 j 每次都回退到首元素我们再举一个例子看看 j 会怎么变化。第二个例子目标串主串 S abcababca, 模式串子串 T abcabx。BF算法执行过程如下图所示在步骤 ① 中前5个字符完全相等根据上一个例子的经验已知模式串T中第一位字符与第二位、第三位不等后续会根据next[]数组计算得出步骤 ②③ 都是多余的直接省略。与上个例子不同的是这里的模式串 T 的首位字符 a 与 T 第四位的 a 相等第二位的 b 与第五位的 b 相等而在 ① 中,第四位的 a 第五位的 b 已经与主串 S 中的相应位置比较过了是相等的。因此可以断定,T 的首字符 a、第二位的字符 b 与 S 的第四位字符和第五位字符肯定也是相等的所以 ④⑤ 这两个比较得出字符相等的步骤也可以省略。总结上面两个例子在KMP算法中主串的 i 值是不需要回溯的。所以我们只需要考虑变化的 j 值模式串 j 值的变化通过观察可以发现当主串和模式串不匹配时下一步 j 该指向哪个元素只与模式串 T 本身有关系。当发现有相同的字符j 的变化也就会不同。在KMP中当主串和模式串不匹配时, 下一步 j 值的多少取决于当前字符之前的串的前后缀的相似度。next数组基础知识在我们计算next数组之前我们先讲解一些基础知识。前缀字符串的开头例如字符串abcd的前缀为a, ab, abc, abcd。在KMP算法中使用的前缀为真前缀既不包括原字符串abcd的前缀。真前缀a, ab, abc后缀字符串的结尾在KMP算法中同样使用的是真后缀(bcd,cd,d)。最长公共前后缀最长的相等的前缀与后缀例如字符串ABCxyzABC的最长公共前后缀为ABCABCXYABC的真前缀AAB,ABC, ABCx, ABCxy, ABCxyz, ABCxyzA, ABCxyzABABCXYABC的真后缀BCxyzABC, CxyzABC, xyzABC, yzABC, zABC,ABC, BC, C前缀表存储每一个前缀的最长公共前后缀的长度。举例若模式串 Tabaaabaaca。next数组把 T 串各个位置的 j 的变化定义为数组 nextnext 的长度就是 T 串的长度。主串和模式串不匹配时下一步 j 的值由 next[j] 决定。例如目标串 Sabcaba, Taba, 根据前缀表求出 next[-1,0 0], 当 j2 时发生不匹配, next[2]0, 下一步 j 将等于 0 进行字符匹配。前缀表和next数组的关系前缀表存储每一个前缀的最长公共前后缀的长度next数组存储的是模式串向右移动到next值的位置这个值与前缀的最长公共前后缀的长度有关所以next数组是可以由前缀表生成的。用前缀表生成一个next数组很容易将前缀表每一位都向后移动1位最后一位舍去并在第一位补一个-1就得到了next数组。如果有同学不理解这个关系还可以看一下手动推理过程Tabaaabaaca位置0上的元素a前面没有子串令next[0]-1位置1上的元素b前面的字符串为a字符串a没有最长公共前后缀next[1]0位置2上的元素a前面的字符串为ab,ab没有最长公共前后缀next[2]0位置3上的元素a前面的字符串为aba最长公共前后缀为anext[3]1位置4上的元素a前面的字符串为abaa最长公共前后缀为anext[4]1位置5上的元素b前面的字符串为abaaa最长公共前后缀为anext[5]1位置6上的元素a前面的字符串为abaaab最长公共前后缀为abnext[6]2位置7上的元素a前面的字符串为abaaaba最长公共前后缀为abanext[7]3位置8上的元素a前面的字符串为abaaabaa最长公共前后缀为abaanext8]4位置9上的元素a前面的字符串为abaaabac没有最长公共前后缀next[9]0同时在KMP算法中next数组的计算这篇博客中提到了一个地方为什么有些next数组是0,1开头而有些next数组是-1,0开头-1,0开头与0, 1开头的next数组本质是一样的。实际上以0, 1开头的next数组就是以-1,0开头的next数组每一项加1得到的。出现这种情况的原因在于模式串起始的索引值在程序中一个数组的索引的起始值为0然而在考试和书中给的模式串起始值是多从1开始。所以在考试中遇到的next数组通常是以0, 1开头而一些程序或教程中的next数组是以-1, 0开头。注在考试中通常会给模式串的索引或者会给next值的前两项在答题时要按照题目中的要求写next数组。代码实现next数组的代码实现, 可以计算出当前匹配串 T 的 next 数组void get_next(string T, int *next) { next[0] -1; int i 0; int j -1; while(i T.size() - 1) { //T[i]表示后缀的单个字符 //T[j]表示前缀的单个字符 if(j -1 || T[i] T[j]){// i; j; next[i] j; } else { //如果字符不相同则j值回溯 j next[j]; } } }KMP代码实现int KMP(string S, string T) { int ans -1; // i用于遍历主串S int i 0; // j用于遍历匹配串T int j 0; int next[255]; // 这里初始长度为255,需自行调整 // 对T做分析得到next数组 get_next(T, next); while (i S.size()) { // 匹配成功则继续向下一个字符进行匹配 if (j -1 || S[i] T[j]) { i; j; } // 匹配失败进行回溯 else { // j回溯到合适的位置 j next[j]; } if (j T.size()) { ans i - T.size(); break; } } return ans; }时间复杂度令 n 为主串长度m 为要匹配的子串长度。
KMP模式匹配算法——详细讲解、清晰易懂
MP是由基础的字符串匹配BF算法改进而来的KMP模式匹配算法原理目标串主串 S heloohello, 模式串子串 T hello。我们要从主串 S 中找到子串 T 的位置。如果使用BF算法步骤如下图所示。在 ① 中当 S 和 T 不匹配时BF算法的操作是主串 S 回退到 i-j1从本次匹配的初始位置后移一位图中步骤②的位置匹配串 T 回退到 j 0 (初始位置, 然后执行 ②③④⑤⑥ 步依次进行匹配但所有这些步骤一定都是必需的吗在步骤 ① 中单看模式串 T前三个字符均不相等h ! e ! l同时S 和 T 串前三个字符又相匹配那么模式串 T 的首字符h 自然不可能和主串 S 的第二、三位字符相等。所以步骤②③都是多余的。这是KMP算法的关键所在如果我们知道 T 串中哪些字符相等也是关键点后续会讲那么有些步骤就可以省略。因此只需要保留①④⑤⑥的步骤即可。从下图可以看出指针 i 是不是一直没有回溯这就是KMP的妙处所在。在KMP中指针 i 永远不会回溯只有指向模式串的指针 j 会发生回溯。在本例中 j 每次都回退到首元素我们再举一个例子看看 j 会怎么变化。第二个例子目标串主串 S abcababca, 模式串子串 T abcabx。BF算法执行过程如下图所示在步骤 ① 中前5个字符完全相等根据上一个例子的经验已知模式串T中第一位字符与第二位、第三位不等后续会根据next[]数组计算得出步骤 ②③ 都是多余的直接省略。与上个例子不同的是这里的模式串 T 的首位字符 a 与 T 第四位的 a 相等第二位的 b 与第五位的 b 相等而在 ① 中,第四位的 a 第五位的 b 已经与主串 S 中的相应位置比较过了是相等的。因此可以断定,T 的首字符 a、第二位的字符 b 与 S 的第四位字符和第五位字符肯定也是相等的所以 ④⑤ 这两个比较得出字符相等的步骤也可以省略。总结上面两个例子在KMP算法中主串的 i 值是不需要回溯的。所以我们只需要考虑变化的 j 值模式串 j 值的变化通过观察可以发现当主串和模式串不匹配时下一步 j 该指向哪个元素只与模式串 T 本身有关系。当发现有相同的字符j 的变化也就会不同。在KMP中当主串和模式串不匹配时, 下一步 j 值的多少取决于当前字符之前的串的前后缀的相似度。next数组基础知识在我们计算next数组之前我们先讲解一些基础知识。前缀字符串的开头例如字符串abcd的前缀为a, ab, abc, abcd。在KMP算法中使用的前缀为真前缀既不包括原字符串abcd的前缀。真前缀a, ab, abc后缀字符串的结尾在KMP算法中同样使用的是真后缀(bcd,cd,d)。最长公共前后缀最长的相等的前缀与后缀例如字符串ABCxyzABC的最长公共前后缀为ABCABCXYABC的真前缀AAB,ABC, ABCx, ABCxy, ABCxyz, ABCxyzA, ABCxyzABABCXYABC的真后缀BCxyzABC, CxyzABC, xyzABC, yzABC, zABC,ABC, BC, C前缀表存储每一个前缀的最长公共前后缀的长度。举例若模式串 Tabaaabaaca。next数组把 T 串各个位置的 j 的变化定义为数组 nextnext 的长度就是 T 串的长度。主串和模式串不匹配时下一步 j 的值由 next[j] 决定。例如目标串 Sabcaba, Taba, 根据前缀表求出 next[-1,0 0], 当 j2 时发生不匹配, next[2]0, 下一步 j 将等于 0 进行字符匹配。前缀表和next数组的关系前缀表存储每一个前缀的最长公共前后缀的长度next数组存储的是模式串向右移动到next值的位置这个值与前缀的最长公共前后缀的长度有关所以next数组是可以由前缀表生成的。用前缀表生成一个next数组很容易将前缀表每一位都向后移动1位最后一位舍去并在第一位补一个-1就得到了next数组。如果有同学不理解这个关系还可以看一下手动推理过程Tabaaabaaca位置0上的元素a前面没有子串令next[0]-1位置1上的元素b前面的字符串为a字符串a没有最长公共前后缀next[1]0位置2上的元素a前面的字符串为ab,ab没有最长公共前后缀next[2]0位置3上的元素a前面的字符串为aba最长公共前后缀为anext[3]1位置4上的元素a前面的字符串为abaa最长公共前后缀为anext[4]1位置5上的元素b前面的字符串为abaaa最长公共前后缀为anext[5]1位置6上的元素a前面的字符串为abaaab最长公共前后缀为abnext[6]2位置7上的元素a前面的字符串为abaaaba最长公共前后缀为abanext[7]3位置8上的元素a前面的字符串为abaaabaa最长公共前后缀为abaanext8]4位置9上的元素a前面的字符串为abaaabac没有最长公共前后缀next[9]0同时在KMP算法中next数组的计算这篇博客中提到了一个地方为什么有些next数组是0,1开头而有些next数组是-1,0开头-1,0开头与0, 1开头的next数组本质是一样的。实际上以0, 1开头的next数组就是以-1,0开头的next数组每一项加1得到的。出现这种情况的原因在于模式串起始的索引值在程序中一个数组的索引的起始值为0然而在考试和书中给的模式串起始值是多从1开始。所以在考试中遇到的next数组通常是以0, 1开头而一些程序或教程中的next数组是以-1, 0开头。注在考试中通常会给模式串的索引或者会给next值的前两项在答题时要按照题目中的要求写next数组。代码实现next数组的代码实现, 可以计算出当前匹配串 T 的 next 数组void get_next(string T, int *next) { next[0] -1; int i 0; int j -1; while(i T.size() - 1) { //T[i]表示后缀的单个字符 //T[j]表示前缀的单个字符 if(j -1 || T[i] T[j]){// i; j; next[i] j; } else { //如果字符不相同则j值回溯 j next[j]; } } }KMP代码实现int KMP(string S, string T) { int ans -1; // i用于遍历主串S int i 0; // j用于遍历匹配串T int j 0; int next[255]; // 这里初始长度为255,需自行调整 // 对T做分析得到next数组 get_next(T, next); while (i S.size()) { // 匹配成功则继续向下一个字符进行匹配 if (j -1 || S[i] T[j]) { i; j; } // 匹配失败进行回溯 else { // j回溯到合适的位置 j next[j]; } if (j T.size()) { ans i - T.size(); break; } } return ans; }时间复杂度令 n 为主串长度m 为要匹配的子串长度。
