什么是KMP算法？

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

KMP 与 BF（暴力解法）的区别

KMP 和 BF 唯一不一样的地方在：
当给你一个主串 和 模式串/子串，要你来查找主串是否包含子串，包含就返回 主串中子串的起始的位置，
现在用来遍历主串的变量 i 和 遍历子串的 变量 j，指向字符不匹配时，就意味着 目前 主串中 匹配的字符串 与 子串不相等，也就是说：目前从主串的某一种位置开始，一直到匹配字符不相等的位置之间，与子串不匹配。
KMP ：我主串的 i 并不会回退，并且 j 也不会回到下标0的位置。（这个就是接下来要搞懂的东西）
BF： 我主串的 i 回退 原来 匹配开始的位置，并加一，而 子串的 j 直接回到 下标为0 的 位置，然后继续匹配。

附图

KMP 的 遍历 子串变量 j 的 回退机制

到这里就不用翻了哦，因为截图，达到了最大限度，所以我不得不将其分割成两部分，希望不会影响到大家。

练习（加深 求 next 数组 的印象）

练习一

练习二

接下来，又是推理时间: 如何用程序去 求 k值 / 求 next 数组的元素

Java 实现 KMP 算法

public class Manuscript {
    /*
    * @param str 主串
    * @param sub 子串
    * @param pos 从主串的pos位置开始匹配
    * @return  找到 子串 在主串当中的 下标
    * */
    public static int KMP(String str,String sub,int pos){
        if (str == null || sub == null){
//不管是主串，还是子串为null，你都查找不了 子串 在 主串中的位置
            return  -1;// 此时返回返回-1 表示找不到，或者说无法查找
        }

        int lenStr = str.length();//获取主串的长度
        int lenSub = sub.length();//获取子串的长度

        if(lenStr == 0 || lenStr==0){
 // 这种情况也不用去想，空字符串里面一个元素都没有，肯定也比不了！
            return  -1;
        }
        if (pos < 0 || pos > str.length()){
            // 你规定查找位置不合法，如果不写，很可能会导致越界异常，导致程序终止
            return -1;
        }

        int i = pos;// 从指定的 pos 位置，开始遍历 主串
        int j = 0;// 遍历 子串

        int[] next = new int[lenSub];// 创建一个 next数组，长度 与 子串一致
        getNext(sub,next);// 得到next 数组

        while(i < lenStr && j < lenSub){
            if(j==-1 || str.charAt(i)==sub.charAt(j)){// 这就是主串 和 子串匹配成功的情况
                //  j == -1. 是为了处理i 和 j 指向字符不匹配的情况
                //  j 回退的时候，在next数组中，一直没有 p[j] == p[k]的情况出现
                // j 回退到 -1 的情况，也就是没有相同的真子串情况 p[0]~ p[k-1] != p[j-k] ~ p[j-1]
                // 另外 这个条件需要放在前面，放在后 charAt一读取，就会发生越界异常
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if (j >=lenSub){
            return i-j;
        }
        // 主串 不包含 子串的情况，也就是 i 与 j 不匹配，j 一直在子串的下标0位置待命
        // 即 j < lenSub
        return -1;

    }
    public static void getNext(String sub,int[] next){
        next[0] = -1;
        next[1] = 0;
        int j = 2;// 提前走了一步
        int k = 0;
        while(j< sub.length()){// 遍历 子串
            // p[j] == p[k]
            if(k== -1 || sub.charAt(j-1) == sub.charAt(k)){
                next[j] = k + 1;
                j++;
                k++;
            }else {// p[j] != p[k], j需要回退
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("abababcabcdef","abcd",0));//7
        System.out.println(KMP("abababcabcabcdef","abcdf",0));// -1
        System.out.println(KMP("abababcabcabcdef","ab",0));//0
    }
}

附图 （讲解重要部分）

附图 1（主串 查找 子串的过程）

附图 2 （next数组，实现注意情况）

C 实现 KMP 算法

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char*sub, int* next, int lenSub)
{
	next[0] = -1;
	next[1] = 0;
	int j = 2;
	int k = 0;
	while (j < lenSub)
	{
		if (-1 == k || sub[j - 1] == sub[k])
		{
			next[j] = k + 1;
			k++;
			j++;
		}
		else
		{
			k = next[k];
		}
	}

}

int KMP(char* str, char* sub, int pos)
{
	assert(str&&sub);//判断 主串 和 子串是否为 NULL 指针
	int lenStr = strlen(str);
	int lenSub = strlen(sub);
	if (lenStr==0 || lenSub==0)
	{
		return -1;
	}
	if (pos < 0 || pos >= lenStr)
	{
		return -1;
	}

	int* next = (int*)malloc(sizeof(int)*lenSub);
	assert(next);// 判断空间是否开辟失败
	GetNext(sub, next,lenSub);

	int i = pos;
	int j = 0;

	while (i < lenStr && j < lenSub)
	{
		if (-1 == j || str[i] == sub[j])
		{
			j++;
			i++;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	if (j >= lenSub)
	{
		return i - j;
	}
	return -1;
}





int main()
{
	printf("%dn", KMP("abababcabcdef", "abcd", 0));// 7
	printf("%dn", KMP("abababcabcdef", "abcdf", 0));// -1
	printf("%dn", KMP("abababcabcdef", "ab", 0));// 0
	return 0;
}

KMP算法优化 》》 next数组优化 》》 又称 nextval 数组

练习

如果 题目 规定了 next[0] 和 next[1] 的值， 也很简单，就按照这个模式就能写出来，如果运气好，题目规定 next[0] = 0; next[1] = 1，你就在我们这个结果的基础上加一就行了。

文章至此就结束了，希望大家通过这封 KMP 信，能收获颇丰!