学步园

简而言之

用途：

kmp算法用于在【长串】中找【模式串】，并返回【配准的位置】，速度上优于暴力的算法。

暴力法简述：

长串A，短串B，从头（i = j = 0）开始逐个（++）比较，如果A[i] != B[j]，j退回0，i退回本次匹配 i 初始位置，并i++，如此往复。如果在脑中模拟这一过程，好比【短串在长串中
滑动（向右），每滑一步，把短串中的内容从头到尾刷一遍<最坏情况>】，因此时间复杂度为 O（M * N）。

kmp 法简述：

1.我看到的所有讲kmp的blog，都提到kmp 的核心，在于【不回溯长串】，意思是说kmp进行匹配时，i是没有上面暴力法提到的【i退回本次匹配 i 初始位置，并i++】这一步，只增不减。这一下就使得时间复杂度降到了线性，O（M）。

2.如何做到这点，灵魂在于使用了【next数组】。而所谓next数组，是一个关注并记录【前缀后缀】位置信息的数组。用下图来解释，图中S代表长串，P代表短串。

ps：该图来自july博客。

想一个问题，如果已知 

（1）P0 P1 ... Pk-1 == Pj-k Pj-k+1 ... Pj-1；

（2）Pj-k Pj-k+1 ... Pj-1 == Si-k Si-k+1 ... Si-1 且 Pj != Si

是否意味着两件事：

1、匹配位置不是Si-k，得继续去找配准位置；

2、已经确知【P0 P1 ... Pk-1 == Si-k Si-k+1 ... Si-1】，不需要再去比较了，只需要看 Pk 是否等于 Si就可以了。省掉了多次比较。脑中模拟这一次匹配，感觉就像【长串不动，短串很自信地向右狠狠滑了一下，并且从此以后从S0到Si-1都不需要再看了】。

那么，这个信心是谁给它的呢？答案就是上面提到的【next数组】。

也说过了，next数组里存放的信息，关注【前缀后缀】。那么什么是前缀后缀，又关注了些什么呢？

1）简而言之，一个字符串abcdefghijklmn，对于d来说，所谓前缀，即从头开始到d为止的字串：abc；所谓后缀，即从尾倒着往前数直到前缀长度为止的字串：lmn

2）对于n后的下一个字符x，next[x] == d

3）最后要注意到图中所说的【最长】二字

计算这个next数组的时间复杂度同样是线性的，O（N）。

故总的kmp时间复杂度为 O（M+N）。

附个完整代码如下：

#include <iostream>
using namespace std;

void get_next(char *a, int *next)
{
	int len = strlen(a);
	int i = 0, j = -1;
	next[0] = -1;
	
	while(i < len - 1)
	{
		if(j == -1 || a[i] == a[j])
		{
			++i; ++j;
			if(a[i] != a[j])        //优化 
				next[i] = j;
			else
				next[i] = next[j];
		}
		else
		{
			j = next[j];
		}
	}	
}

int kmp(char *src, char *tag)
{
	int next[255];
	get_next(tag, next);
	
	int lens = strlen(src), lent = strlen(tag);
	int i = 0, j = 0;
	
	while(i < lens && j < lent)
	{
		if(src[i] == tag[j] || j == -1)
		{
			++i; ++j;
		}	
		else
		{
			j = next[j];
		}	
	}
	if(j == lent)
		return i - j;
	else
		return -1;
}

int main(void)
{
	char src[] = "DABCDABDE";
	char tag[] = "ABD";

	cout << kmp(src, tag) << endl;
		
	return 0;
}