KMP算法的代码看起来很简单，但是想要理解其原理却非常的困难。在这里建议初学者多多找讲解KMP算法的视频来观看，个人认为视频更容易帮助人来理解，只通过文字的讲解看起来是十分困难的，还有个人也要多多的思考。当理解了原理过后，具体的代码写起来就很简单了，它与BF算法十分相似，只是多了个求next数组的步骤。

KMP算法由匹配部分与求next数组部分，两部分组成。 匹配时的算法特点： （1）需要有一个指向主串的指针i与指向模式串的指针j，且两者都应该初始化为0； （2）i永不回退，只回退j，且j的回退步数由next数组决定，即j=next[j]; （3）循环条件为i<s_length&&j<t_length。

KMP算法：

s是主串，t是子串,next表示next数组
int KMP(char s[],char t[],int next[])
{
	int i=0;
    int j=0;
    int s_length=strlen(s); //求字符串s的长度
    int t_length=strlen(t); //求字符串t的长度
    while（i<s_length&&j<t_length）
    {
    	if(j==-1||s[i]==t[j]) //当j等于-1的时候退化到BF算法
        {
        	i++;
            j++;
        }
        else
        {
        	j=next[j]; // i永不回退，只回退j
        }
	}
    if(j==t_length)
    {
    	return i-j;
    }
    else
    {
    	return -1;
    }
}

next数组的特点： （1）求next数组时需要一个前缀指针j以及后缀指针i,且前缀指针j应初始化为-1，后缀指针应初始化为0； （2）next数组的首元素为-1,即next[0]=-1; （3）因为要求每个子串的最长相等前后缀，故循环条件为i<length。 下面是求next数组的过程：

//str指向模式串，next用来保存next数组 
void GetNext(char* str, int* next)
{
	int j = -1; //j是模式串的前缀
	int i = 0; //i是模式串的后缀
	next[0] = -1;
	int length=strlen(str);
	while (i < length)
	{
		if (j == -1 || str[i] == str[j])
		{
			i++;
			j++;
            //注意记录next数组里面的值哦
			next[i] = j; //如果第i个字符与第j个字符相同,那么next[i]的值就应该等于前缀j的值
		}
		else
		{
			j = next[j]; //否则的话,j跳到拥有最长相等前后缀的那个位置，再次比较
			             //其实这个过程就相当于求模式串的子串的最长相等前后缀
		}
	}
}

通过以上的观察可以看到，求next数组函数里的循环体部分与KMP算法的匹配部分的循环体部分几乎是一样的，除了循环条件。为什么会这样呢？其实求next数组的过程就相等于，模式串是主串，而模式串的子串又相当于模式串，然后再求两者的匹配过程。详细地说，就是子串为str[0]， str[0]str[1],str[0]str[1]str[2]…………时，每个子串都与主串匹配了一遍。

以下详细说一下：当str[i]!=str[j]时，为什么j要回退到next[j]这个位置？ alt

当str[i]!=str[j]时，应该就先

(1)比较str[0]与str[i],即j=0，比较str[j]与str[i],设k=0;

(2)如果相等，则继续比较，str[0]与str[i-1],即j++

如果相等，又继续比较，str[1]与str[i]，即j++

(3) ……

继续比较,直到s[j]!=s[i]时，那么就找到了最长相当前后缀。

但实际上，上述需要比较多少次，我们是可以直接通过next数组知道的。即比较次数可以由next[j]来快速确定。