神马文学网KMP：在一个长字符串中匹配一个短子串的无回溯算法
来源：百度文库 编辑：神马文学网 时间：2024/04/29 22:37:31
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[i] == 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){
if (j ==0 || T[i] == T[j])
{
++i;
++j;
next[i] = 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[i] == T[j])
{
++i; ++j;
if (T[i] == T[j])
next[i] = next[j];
else
next[i] = j;
}
else j = next[j];
}
}
现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了：
相当简单：
int KMP(char* S, char* T, int pos)
{
int i=pos, j=1;
while (i){
if (S[i] == T[j]){ ++i; ++j; }
else j = next[j]
}
if (j>T[0]) return i-T[0];
else return 0;
}
和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)
感谢伟大的算法大师们的精彩算法，和严老师严谨求实的态度。
先看看最“朴素”的算法：
///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[i] == 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){
if (j ==0 || T[i] == T[j])
{
++i;
++j;
next[i] = 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[i] == T[j])
{
++i; ++j;
if (T[i] == T[j])
next[i] = next[j];
else
next[i] = j;
}
else j = next[j];
}
}
现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了：
相当简单：
int KMP(char* S, char* T, int pos)
{
int i=pos, j=1;
while (i){
if (S[i] == T[j]){ ++i; ++j; }
else j = next[j]
}
if (j>T[0]) return i-T[0];
else return 0;
}
和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)
感谢伟大的算法大师们的精彩算法，和严老师严谨求实的态度。
KMP：在一个长字符串中匹配一个短子串的无回溯算法
KMP：在一个长字符串中匹配一个短子串的无回溯算法
KMP字符串匹配算法笔记
KMP字符串模式匹配
KMP字符串模式匹配zhuan
KMP算法
KMP算法
C语言中在一个串中查找给定字符的第一个匹配之处函数
入侵检测系统中模式匹配算法的研究
一个简单的算法Crackme
算法： 怎样判断一个点在多边形中（凸， 凹）
KMP算法_飞花如梦，阳光灿烂的日子
Java中使用正则表达式实现字符串匹配
Java中使用正则表达式实现字符串匹配_似虫非虫
Java中使用正则表达式实现字符串匹配
如何将一个字符串加密
完全掌握KMP算法思想
完全掌握KMP算法思想
字符串匹配问题
如何轻松编写一个强大的字符串分解器(2)
在文件中搜索字符串。
刀具的两个适用性和一个匹配性(3)
刀具的两个适用性和一个匹配性(2)
刀具的两个适用性和一个匹配性(1)