一、算法介绍

KMP主要应用在字符串匹配上的算法，该算法是由Knuth，Morris和Pratt三位学者发明的，故称之为KMP算法

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

现在有两个字符串分别为aabaabaafa和aabaaf，现在我们要用后者去匹配前者，在没有用KMP算法之前，只能一个一个枚举进行匹配，这时我们不难发现到会有一些公共的前缀被频繁使用，但是暴力枚举并没有利用到这一点，所以使得算法不能很好利用到这个性质。

而KMP算法则很好利用到了这个特性，引用了一个叫做前缀表的东西来记录当前模式串最大的前后缀，通俗来说该表记录的是模式串(要找的串)与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配，通常使用next数组来进行记录。这里来举例子来帮助理解。

用该图片可以看到，如果可以利用好前缀这个特性，就可以极大节约匹配次数和匹配时间，从而提高算法的效率。
在考研中我们上文构造的next数组需要右移，然后对了第一个数字置为-1即可。

二、构造next数组

那么该如何利用构造这个next数组呢？这里介绍一下利用前后缀匹配法来进行构造。

前缀：除了尾字符以外的任意字串

后缀：除了首字符以外的任意字串

既然明白了为什么要进行构造，已经构造原理，那就来用代码实现吧

实现思路为：

• 用j来指向当前后缀
• 先进行寻找当前子串的最长前后缀大小，即和s[i]相同的最左边的字符
• 如果当前字符能和j所指向字符一致便对j进行++操作，然后将其next[i] = j
• 如果指向不一致，直接进行next[i] = j
• 说明：这里解释为什么最后操作都是一致，当能找到s[i] == s[j]是，即可说明之前的next数组有可能存在一组以s[i]结尾的前后缀，此时的j就是在s[i]之前，最大前后缀的大小，如果不存在也无妨，说明该前后缀是以s[i]最大的前后缀,进行++后，便得到了当前最大前后缀的大小
• 当没找到时，说明我们需要回跳到数组最开始位置进行比较，此时j就为0

void kmp::init_next()
{
	_next[0] = 0;
	int j = 0;
	for (int i = 1; i < _n; i++)
	{
        //这里不可用if，因为要不断进行搜寻
		while (j && _s[i] != _s[j])
		{
			j = _next[j - 1];
		}
		if (_s[i] == _s[j])
		{
			j++;
		}
		_next[i] = j;
	}
}

三、查找

当有了next数组之后，kmp算法最大难点便被攻克，可以利用next数组来进行匹配字串，匹配大思路和暴力匹配思路一样，便不再赘述，只不过当遇到字符不一致地方时，我们便利用当前字符前一个字符的前缀表中的值来进行搜寻，然后继续重复操作即可

为什么要利用前一个字符呢？因为当前已经不匹配了，如果不利用前一个字符，而利用当前的字符，当前字符所对应的必然不匹配，而前一个则可能匹配，而且前一个所对应的前缀必然是局部最优解

int kmp::strstr(string& s)
{
	int n = s.size();
	if (n == 0) return -1;
	int j = 0;
	for (int i = 0; i < n; i++)
	{
		while (j && s[i] != _s[j])
		{
			j = _next[j - 1];
		}
		if (s[i] == _s[j]) j++;
		if (j == _n) return i - _n + 1;
	}
	return -1;
}

四、优化

不难注意到，当字符为aaa时，第三个字符不匹配时，会跳到第一个字符，用该字符来进行匹配，但是用肉眼一看这三个字符是一样的，不管谁来匹配结果都是一样的。所以为了解决这个问题，提出了如下的方案：当发现跳转的字符和当前字符一致时，跳到跳转字符的最长前缀作为该前缀表的值。

前字符最长前缀必然是和自己不一样的值(s[0] == s[i] 这种情况除外)

所以，便可用这样的思想对next数组进行优化，在构造完next数组后，对next数组在进行检查即可，确保跳转的值和自身不一样，优化后的数组称之为next_val数组。

void kmp::init_next_val()
{
	_next_val[0] = 0;
	for (int i = 1; i < _n; i++)
	{
		if (_s[i] == _s[_next[i]])
		{
			_next_val[i] = _next_val[_next[i]];
		}
		else
		{
			_next_val[i] = _next[i];
		}
	}
}

那可不可以不借助next数组来进行构造，当然可以了，只用在找到当前最长前后缀后加一个判断，确保跳转的值不一样即可

void kmp::init_next_val()
{
	_next_val[0] = 0;
	int j = 0;
	for (int i = 1; i < _n; i++)
	{
		//正常使用next数组构造方式
		while (j && _s[i] != _s[j])
		{
			j = _next_val[j - 1];
		}

		if (_s[i] == _s[j]) j++;
		//这里进行判断，确保两者不一样
		if (j == 0 || _s[i] != _s[j])
		{
			_next_val[i] = j;
		}
		else
		{
			_next_val[i] = _next_val[j];
		}
	}
}

五、代码总览

kmp.h

class kmp
{
public:
	
	kmp(string& s)
		:_s(s)
	{
		_n = s.size();
		_next.resize(_n);
		_next_val.resize(_n);
		init_next();
		init_next_val();
	}

	void init_next();
    //无next版本
	void init_next_val();
    //有next版本
	void init_next_val(int);
	int strstr(string& s);
	void Print();
	void Print_Val();

private:
	int _n;
	vector<int> _next;
	vector<int> _next_val;
	string _s;
};

kmp.cpp

#include "kmp.h"

void kmp::init_next()
{
	_next[0] = 0;
	int j = 0;
	for (int i = 1; i < _n; i++)
	{
		while (j && _s[i] != _s[j])
		{
			j = _next[j - 1];
		}
		if (_s[i] == _s[j])
		{
			j++;
		}
		_next[i] = j;
	}
}

void kmp::init_next_val()
{
	_next_val[0] = 0;
	int j = 0;
	for (int i = 1; i < _n; i++)
	{
		//正常使用next数组构造方式
		while (j && _s[i] != _s[j])
		{
			j = _next_val[j - 1];
		}

		if (_s[i] == _s[j]) j++;
		//这里进行判断，确保两者不一样
		if (j == 0 || _s[i] != _s[j])
		{
			_next_val[i] = j;
		}
		else
		{
			_next_val[i] = _next_val[j];
		}
	}
}

void kmp::init_next_val(int)
{
	_next_val[0] = 0;
	for (int i = 1; i < _n; i++)
	{
		if (_s[i] == _s[_next[i]])
		{
			_next_val[i] = _next_val[_next[i]];
		}
		else
		{
			_next_val[i] = _next[i];
		}
	}
}

int kmp::strstr(string& s)
{
	int n = s.size();
	if (n == 0) return -1;
	int j = 0;
	for (int i = 0; i < n; i++)
	{
		while (j && s[i] != _s[j])
		{
			j = _next_val[j - 1];
		}
		if (s[i] == _s[j]) j++;
		if (j == _n) return i - _n + 1;
	}
	return -1;
}

void kmp::Print()
{
	for (auto& e : _next)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

void kmp::Print_Val()
{
	for (auto& e : _next_val)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}

以上便是kmp算法的全部内容
完！