KMP算法

什么是KMP算法

KMP算法一种改进的模式匹配算法，是D.E.Knuth、J.H.Morris、V.R.Pratt于1977年联合发表。KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配，后文主串和模式串匹配，子串和模板串匹配。先在开头约定，本文用pat表示模式串，长度为 M，txt 表示文本串，长度为N。KMP 算法是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。

几个最基本的概念：

字符串的前缀：从主串下标0开始的子串称为主串的前缀
字符串的后缀：从主串下标大于0的位置到结尾的子串称为主串的后缀
目标串：也就是主串，简单说就是那条比较长的串txt
模式串：也就是那条短的，用来匹配的串pat
kmp算法的目的：在\(O(m+n)\)的时间复杂度的内进行串匹配，也就是在目标串中找到模式串，并返回目标串中模式串的第一个字符下标

暴力做法

KMP可以解决串的模式匹配，但是一般我们解决这个问题首先想到的是暴力做，什么也不管，直接两个for循环。暴力匹配也叫朴素的模式匹配。

从主串和子串的第一个字符开始，将两字符串的字符一一比对，如果出现某个字符不匹配，主串指针i回溯到第二个字符，子串指针j回溯到第一个字符再进行一一比对。如果出现某个字符不匹配，主串回溯到第三个字符，子串回溯到第一个字符再进行一一比对…，一直到子串字符全部匹配成功。这样时间复杂度为\(O(N*M)\)

//暴力解
for(int i=0;i<N;++i){
	int cursor=i,j=0;
	for(;j<M;++j){
		if(pat[j]!=txt[cursor]) break;
		++cursor;
		}
	if(j==M) return i;
	}

KMP算法

暴力解发的时间复杂度为\(O(N*M)\)，是因为做了许多不必要的位置i的回溯。KMP算法正是对该暴力解的优化。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯位置i，只回溯j指针

那么问题就是如果发生失配时，j进行回溯，j应该回溯到什么位置才能保证算法的正确性?

看到上述的解释，有点动态规划的味道了，但是在实际的过程中我们是对匹配串pat做相应的预处理来达到这种效果的。如果说，j不是回溯到0，而是回溯到模式串pat中间的某一个位置，那么怎么知道在应该回溯到pat的哪个位置呢，我们不先介绍KMP算法的next数组（KMP算法最核心的部分就是next数组了），因为直接介绍代码会很难理解。

首先，得明白构造next数组的原理：其实就是从pat串出发，确定pat中出现的重复公共串，利用先前遍历的结果避免j回溯不必要的位置，这样就能在回溯中确定位置。换句话说就是利用前后缀的相同字符处理。

next数组的构建

next数组的构建是从其pat的前缀和后缀相同串长度确定，换一句话说，next[i]指的是当前pat[0:i]范围内的前缀和后缀相同串的最长值，举个例子由pat=abcabcd:

就比如abcabcd,此时next数组的长度是7，next[0]毫无疑问是0，因为它没有后缀
要确定next[2]，可以清楚知道abc的其各前缀和各后缀都没有相同子串，因此next[2]=0
要确定next[3]，可以清楚知道abca存在前缀abc和后缀a的相同子串a，因此next[3]=1。这就是next数组的含义

上面对每个next[i]数组的处理,要前缀和后缀相同串长度，需要经过多次比较确定，就比如pat=abcabcd,要确定next[3]:

①前缀a,后缀bca的相同长度为1
②前缀ab,后缀ca的相同长度1
③前缀abc，后缀a的相同长度为1`

因此next数组的确定，按暴力方法时间复杂度会达到\(O(M^2)\)，这以暴力匹配没什么区别，因此必须想办法看是否有O(m)的方法来确定next数组

快速构建next

假设我们已经求得了next[i-1]的值，并且next[i-1]=now对应的最长前缀和后缀相等长度为now，那么我们再求next[i]的时候也会有两种情况,就比如pat=abcabdddabcabc：

//pat匹配串
      0 1 2 3 4 5 6 7 8 9 10 11 12 13
      a b c a b d d d a b c  a  b  c
next  0 0 0 1 2 0 0 0 1 2 3  4  5  3

情况1：pat[now]==pat[i]，这种情况直接next[i]=now+1
情况2：pat[now]!=pat[i]。
- 这种情况，就比如要确定next[13]，由于next[12]=5,由于pat[5]!=pat[13]，因此不能为情况1，但也不能直接设置为0，需要沿着next回溯分析，这是因为前缀pat[0:now-1]一定有重复。
- 分析：当我们跳到now=next[12]=5时候，发现pat[5]!=pat[13]，这就说明pat[now]不符合，但是pat[0:now-1]前可能存在一个符合长度0<k<5的子串，那么我们得沿着next跳到下一个now=next[now-1],比较pat[now]是否与pat[13]相等，上述步骤循环，直到=(pat[now]==pat[i])时，next[i]=now+1；或者now=0且pat[now]!=pat[i],则next[i]=0。
- 示例1：就比如要确定next[13]，此时now=pat[12]=5，因为pat[13]!=pat[now]，更新now=next[now-1]=2,此时now=2,且pat[13]==pat[now]，所以next[13]=now+1=3
- 示例2：再比如要确定next[5]，此时now[4]=2,然而pat[5]!=pat[now]，因此更新now=next[now-1]=0,因为now=0且pat[5]!=pat[now]，因此pat[5]=0

这样构建next数组的复杂度只有O(M)

//确定next数组代码
	int m=pat.size();
	vector<int>next(m,0);
	for(int i=1,now=0;i<m;++i){
		while(now>0&&pat[i]!=pat[now]){
			now=next[now-1];
		}
		if(pat[i]==pat[now]) ++now;
		next[i]=now;
	}

KMP算法完整代码

有了上述的分析，我们可以较容易的写出KMP的完整代码，利用next数组进行匹配：

int maxReapting(string txt,string pat){
	int n=txt.size(),m=pat.size();
	vector<int>next(m,0);
	for(int i=1,now=0;i<m;++i){
		while(now>0&&pat[i]!=pat[now]){
			now=next[now-1];
		}
		if(pat[i]==pat[now]) ++now;
		next[i]=now;
	}
	int startIndex=0;
	for(int i=0,j=0;i<n;++i){
		while(j&&txt[i]!=pat[j]) j=next[j-1];
		if(txt[i]==pat[j]){
			++j;
			if(j==m) return i-m+1;
		}
	}
	return -1;
}

首先是for循环，最多循环m次，对于++j这行代码，每次最多加一次，所以在这m次循环中，j最多加上m.下面再看其中的while循环。

while循环的功能就是把j往回跳，而由于最后j >= 0所以，在m次for循环中，j最多回跳了m次，所以总的复杂度最多是O(2m)也就是O(m)

从而kmp算法的整体复杂度就是O(n + m)

多个匹配

上面的KMP算法只看是否有匹配项，当存在多个匹配项时，想得到这些匹配项的起始位置：代码改动如下：

vector<int> maxReapting(string txt,string pat){
	int n=txt.size(),m=pat.size();
	vector<int>next(m,0),ans;
	for(int i=1,now=0;i<m;++i){
		while(now>0&&pat[i]!=pat[now]){
			now=next[now-1];
		}
		if(pat[i]==pat[now]) ++now;
		next[i]=now;
	}
	int startIndex=0;
	for(int i=0,j=0;i<n;++i){
		while(j&&txt[i]!=pat[j]) j=next[j-1];
		if(txt[i]==pat[j]){
			++j;
			if(j==m){
				ans.push_back(i-m+1);
				j=next[j-1];
			}
		}
	}
	return ans;
}

题目：

文章来源：

KMP算法详解

算法基础（六）：KMP算法详解（next数组详解

KMP算法详解

ps：东哥的KMP算法解析更像有限状态机的解题，容易理解，但总觉得失去了KMP原汁原味的解题思路以及最优的复杂度