| 词条 | KMP |
| 释义 | § 简介 KMP：在一个长字符串中匹配一个短子串的无回溯算法。 先看看最“朴素”的算法： ///find a template in a string. int Index(char *S, char *T, int pos) { int i=pos,j=1; while(i <= S【0】 && j<=T【0】) { if (S == T【j】) { ++i; ++j;} \\\\如果相同，则继续向后比较 else {i = i-j+2; j =1;} \\\\如果不同，就回溯，重新查找 } if (j>T【0】) return i-T【0】; else return 0; }需要注意的是，这里的两个字符串的第一个字节存放的是字符串的长度，所以，无论在任何情况下，请不要忘记，这种写法只能匹配最长255的字符串. 希望比较更长的字符串，请自行更换类型就可以了。或者干脆自己传2个size_t的参数进去. KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后再上面的算法中使用。 § 讲解一下： 当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符前面最多有多少个字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。 举例如下： abcabcddes 0111234111 ^-------------------默认是0 ^^^----------------不能自己相同字符匹配，所以这里者能认为是没有所以是0+1 =1 ^^^------------前面的字符和开始位置的字符相同，所以是2,3,4 ^^^-------不匹配只能取1。 希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。 程序写出来就是： void GetNext(char* T, int *next) { int i=1,j=0; next【1】=0; while( i〈 T【0】 ){ if (j ==0 || T == T【j】) { ++i; ++j; next = j; } else j= next【j】; } } 但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下： void GetNextEx(char *T, char *next) { int i=1,j=0; next【1】 = 0; while(i < T【0】) { if (j == 0 || T == T【j】) { ++i; ++j; if (T == T【j】) next = next【j】; else next = j; } else j = next【j】; } } 现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了： 相当简单： int KMP(char* S, char* T, int pos) { int i=pos, j=1; while (i){ if (S == T【j】){ ++i; ++j; } else j = next【j】 } if (j>T【0】) return i-T【0】; else return 0; } 和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m) |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。