KMP算法初学

具体讲解https://blog.csdn.net/v_JULY_v/article/details/7041827

两个概念得需要知道：

前缀：指的是字符串的子串中从原串最前面开始的子串，如abcdef的前缀有：a,ab,abc,abcd,abcde
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如abcdef的后缀有：f,ef,def,cdef,bcdef

如果给定文本串S“BBCABCDABABCDABCDABDE”，和模式串P“ABCDABD”，

普通的方法就是暴力，从头开始遍历如果不匹配就让字串向后平移一位，平且需要重新开始对比，重复此过程直到找到对应的字串，非常耗时。

KMP算法不需要重新对比，只需要找到最长的公共前后缀然后将前缀移至后缀，并且继续从字串的当前位置开始比较，比如两个串，主串abbababaabbab，模式串abbaa,我们从1开始遍历（红色表示不匹配，蓝色表示最长公共前缀后缀）

1.abbababaabbab

   abbaa

第五位不同，且最长公共前缀后缀长度为1，将模式串前缀移至对应的后缀上，继续从第五位开始比较不需要回溯，不断的重复直到找到对应的子串：

abbababaabbab

      abbaa

......（这是我理解的）

next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1（0代表没有，-1代表就不存在前缀后缀），则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。

int KmpSearch(char* s, char* p)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
            //next[j]即为j所对应的next值      
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}

KMP算法初学

原文：https://www.cnblogs.com/ygy0420/p/13454339.html