KMP算法

介绍

          KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)或O(max(m,n))。广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域。

---

问题

问题：对于字符串查找问题：给定文本串string和模式串patterm， 从文本串string中找出模式串pattern第一次出现的位置。

暴力求解(Brute Force) :时间复杂度O(m*n)，空间复杂度O(1)

KMP算法：时间复杂度O(m+n)或O(max(m,n)),空间复杂度O(M)

---

准备          

       我们先看下这样一个例子：假如字符串string为"ABCABDADBA ",进行匹配的模板pattern字符串为“ABD”,如何找出模式串pattern第一次出现的位置？我们先看暴力求解(Brute Force) ：

 

//暴力算法 时间复杂度O(M*N)，空间负责度O(1);
int BruteForce(const char *s,const char *p)
{
	const int size =static_cast<int>(strlen(p));
	const int nLast =static_cast<int>(strlen(s)) - size ;
	int i = 0;
	int j=0;
	while (i<=nLast&&j<size)
	{
		if(s[i+j]==p[j])
		{
			j++;
		}
		else
		{
			i++;
			j = 0;
		}
	}
	if(i>=size)
	{
		return i;
	}
	return -1;
}

       

      上诉代码有这样一个问题：什么问题呢，就是s[i+j]不等于p[j]的时候，我们不想让j=0;而是将字符串p向后移动若干个位置,接着进行匹配。既然我们不想让j=0;该如何将p进行后移呢？移动多少个位置呢？（这个问题我们先放在这里）。

占时先不考虑p怎么进行移动，接下来我们再看一个例子：假如给定有这样一个字符串“CDEFCDABCD”,求next得值（如下图）。如何求字符串的next呢？接下来我们就求下next（*KMP解法的一个关键点）：

例如:求A(也就是index=6)的next值，我们把A舍去，只看index 0到5的，求下K前/后缀相等字符的最大长度max{0-5}。

---

分析BF和KMP思路

   既然我们知道给定任意一个字符串，我们就能得到该字符串的next。那么我们就利用next做点事情。接下来我们看下BF和KMP的思路。（KMP中模式串pattern利用到了next的求法，换句话说求模式串pattern的K前缀和K后缀）。

   假设当前文本串string匹配到i位置，模式串pattern串匹配到j位置。

   BF算法中：

    如果当前字符匹配成功，即string[i+j]==patterm[i]，令i++, j++，继续匹配下一个字符;

    如果失配，即string[i+j] ≠patterm[i]，令i++, j=0，即每次。匹配失败的情况下，模式串pattern相对于文本串string向右移动了一位。

   KMP算法中：

    如果当前字符匹配成功，即string[i+j]== pattern[j]，令i++, j++, 继续匹配下一个字符;

    如果失配，即string[i+j]≠patterm[i], 令i不变，j=next[i],(这里，next[]≤j-1), 即模式串pattern相对于文本串string向右移动了至少1位 (移动的实际位数j-nextj]≥1)。

   

 

---

代码（语言C++）

#include <iostream>
#include <vector>
using namespace  std;

void GetNext(const char* p, vector<int> &next)
{
	const int len = static_cast<int>(strlen(p));
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < len - 1)
	{
		if (k == -1 || p[j] == p[k])
		{
			++j;
			++k;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
}

int KMP(const char* s, const char* p)
{
	const int sSize = static_cast<int>(strlen(s));
	const int pSize = static_cast<int>(strlen(p));
	int i=0;
	int j=0;
	vector<int> next(pSize);
	GetNext(p, next);
	while (i<sSize&&j<pSize)
	{
		if(j==-1||s[i]==p[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= pSize)
		return (i - pSize);
	return -1;
}

int main()
{
	const char* s = "ImNlikiOrImNanHui";
	const char* p = "ImNanHui";
	int index = KMP(s, p);
	cout << index << endl;
}

运行结果：9