KMP算法（求解字符串匹配）

提示：可搭配B站比特大博哥视频学习：传送门 （点击）

目录

前言

图解

代码

---

前言

        KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特一莫里斯―普拉特操作（简称KMP算法)。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。来自

-------百度百科。

区别: KMP和BF唯一不一样的地方在，我主串的i并不会回退，并且j也不会移动到0号位置
 

图解

1.为什么主串下标j不用回退到0：

 现在是在子串2号位置匹配失败，j回退到0，i回退到1，此时两个字符串还是不匹配

2.j回退的位置：主串下标用i表示，字串下表用j表示

引出next数组

KMP的精髓就是next数组:也就是用next[j]= k;来表示，不同的j来对应一个k值，这个k就是你将来要移动的j要移动的位置。
而k的值是这样求的:
1、规则:找到匹配成功部分的两个相等的真子串(不包含本身)，一个以下标0开始，另一个以j-1下标结尾。
2、不管什么数据next[0] = -1;next[1] =0;在这里，我们以下标来开始，而说到的第几个第几个是从1开始;
练习：

举例：

第二个数组，第一个元素a默认是-1，

第二个元素b默认是0，

第三个元素c判断a到c前面一个元素b之间区间，有没有从a开始以a结束的两个相等的真子串，没有，因为a之后就是b了，

第四个元素a，然后看他前面abc中，没有两个相等的真子串，

第五个元素b，前面abca中，从前看有a，从后看有a，所以有两个相等的真子串，长度为1，

第六个元素c，前面abcab中，从前看有ab，从后看有ab，所以有两个相等的真子串，长度为2，

第七个a，前面abcabc中，前面有abc后面有abc，所以长度是3

第八个元素b，前面abcabca中，前面有abca，后面有abca，所以长度是4

第九个元素c，前面abcabcab中，前面有abcab，后面有abcab，所以长度是5

第14个元素a，前面abcabcabcabcd，前面和后面没有对应的元素，所以长度是0

第二个数组的数字8怎么来的：

首先第一个真子串的起始位置必须从0开始，abcabcab,第二个真子串的终止位置必须是j-1号下标即b(对应值是7(非下标)),abcabcab（从对应值0开始（下标是3））

 总结出来的思路是，第一个位置直接给-1，默认的，第二个给0，因为前一个位置只有一个值，找到最长的前缀（第一个字符串）和后缀（第二个字符串）

代码

前面都和BF算法差不多，只是当出现字符不匹配的时候，j要回退到在next数组中，j对应的值。

而构建next数组时，默认第一个值给-1，第二个值给0（前面只有一个值）

当前一项的值和当前i-1下标的值相等时，同时往后记录，并且将i的位置值设置k+1

当前一项的值和当前i-1下标的值不相等时，则将k退回到上一个位置

void getnext(const char* sub, int* next, int Sublen) {
    next[0] = -1;
    if (Sublen == 1)return;
    next[1] = 0;
    int i = 2;//当前i的下标
    int k = 0;//前一项的k
    while(i< Sublen) {
        //当第一个值就不匹配的时候，++k会回到第一个值
        if (k == -1||sub[i - 1] == sub[k]) {
            next[i] = k+1;
            ++i;
            ++k;
        }
        else
        {
            k = next[k];
        }
    }
}
 
//const常规操作了,防止数据被篡改
//pos代表从主串位置开始找
const int KMP(const char* str, const char* sub, int pos)
{
    //断言及时制止崩溃的程序
    assert(str != NULL && sub != NULL);
    //如果输入为空则返回-1
    if (str == NULL || sub == NULL)
    {
        return -1;
    }
    //计算两个字符串的长度
    int Strlen = strlen(str);
    int Sublen = strlen(sub);
    if (pos < 0 || pos >= Strlen) {
        return -1;
    }
 
    int* next = (int*)malloc(sizeof(int) * Sublen);
    assert(next);
    getnext(sub, next, Sublen);
 
    //定义i为主串的指针，j为字串的指针，下标从0开始
    int i = pos;//从主串指定位置开始找
    int j = 0;
    //当i和j都没有超出字符串的长度时
    while (i < Strlen && j < Sublen)
    {
        //开始匹配
        //当出现j第一个位置就不匹配时，j回到-1下标，此时++i,++j
        //i往后走，j回到第一个位置
        if (j == -1 || str[i] == sub[j])
        {
            i++;
            j++;
        }
        //匹配不成功则讲j回退
        else
        {
            j = next[j];
        }
    }
    free(next);
    //匹配到合适的字符串时
    if (j >= Sublen)
    {
        //直接返回合适字符串的下标
        return i - j;
    }
    //没有找到合适字符串时返回-1
    return -1;
}

测试代码

int main()
{
    printf("%d\n", KMP("ababcabcabcde", "abcd", 0));//对应输出8
    printf("%d\n", KMP("ababcabcabcde", "abcdf", 0));//对应输出-1
    printf("%d\n", KMP("ababcabcabcde", "ab", 0));   //对应输出0
    return 0;
}