字符串匹配问题——KMP算法

字符串匹配问题：给定两个字符串S（主串）和T（模式串），假设n=strlen(S) > strlen(T)=m，判断主串S中是否包含模式T，且返回T在S中所在的起始位置。这里为简单起见，若S包含T，则只返回第一个T所在的位置。

一般的蛮力法如下：

蛮力法在遇到不匹配时，j每次都要回到T的起点，从新开始匹配，这样来看效率就比较低，蛮力法的时间复杂度是O（n*m）。

1、理论

思想：尽量利用已经部分匹配的结果信息，尽量让 i 不回溯，加快模式串T的滑动速度。

先举个启发性的例子，然后引出理论。例子：

结论：从例子中可以看出，每次匹配失败，然后回溯再次从新匹配时（第2、4、5趟），判断当前的S[i]和T[j]是否相等可通过上一趟S和T的匹配结果和T本身的结构信息来得出结论。也就是说，在上一趟S和T匹配结果的基础上，如果知道T本身的结构信息，那么第2、4、5趟的步骤其实是可以省略的，且i可以不用回溯（i不回溯待会儿再来直观理解）。

1.1、模式串T中的信息

抓住部分匹配时的两个特征：

如上图所示，假设S[i]和T[j]不相等后，从T的第k个位置开始和S中的第i个位置比较，那么：

（1）从图的后半部分可得：

                                                                                （1）

（2）从图的后前部分可得： 

                                                                                                （2）

所以，两式联立可得：
                                              （3）

所以，由上面的推理可知，只要提前知道模式串T本身的结构信息，就可以由j计算出k，即下一回T的匹配起点。另外，（3）式可能存在多种不同长度的首尾相等的可能，那么在这样的情况下，肯定是k越大越好，这样一方面可以减少再次匹配的字符数量；另一方面，T向右移动的位置相当S而言也是最慢的，这样也不会错过各种匹配的情况。比如：

令k = next[ j ]，则：

计算next[j]的方法：

由模式T的前缀函数定义易知，next[1]=0，假设已经计算出next[1]，next[2]，…，next[j]，如何计算next[j＋1]呢？设k=next[j]，则已有：

                                                         （4）

此时，比较tk和tj，可能出现两种情况：

（1）tk＝tj：说明t1 … tk-1 tk＝tj-k+1 … tj-1 tj，由前缀函数定义，next[j+1]=k＋1；

（2）tk≠tj：此时要找出t1 … tj-1的后缀中第2大真前缀，显然，这个第2大的真前缀就是next[next[j]]=next[k]。

再比较tnext[k]和tj，此时仍会出现两种情况，当tnext[k]＝tj时，与情况（1）类似，next[j]=next[k]+1；当tnext[k]≠tj时，与情况（2）类似，再找t1 … tj-1的后缀中第3大真前缀。重复执行上述步骤，直到找到t1 … tj-1的后缀中的最大真前缀，或确定t1 … tj-1的后缀中不存在真前缀，此时，next[j+1]=1。

求next数组代码：

void getNext(char T[], int next[])
{
	next[1] = 0;        //从第一个位置开始
	int j = 1, k = 0;   //这里比较巧妙，先不用管什么意思，在相关的地方验证一下，然后就会明白了
	while (j < T[0])
	{
		if ((k == 0) || (T[j] == T[k]))
		{
			j++;
			k++;
			next[j] = k;
		}
		else
			k = next[k];  //往前找
	}
}

2、KMP完整算法

KMP中的核心就是求next数组，之后就没什么关键的了。KMP的时间复杂度为O（n+m），当n>>m时，时间复杂度是O(n)。完整代码如下：

int calLen(char *p)     //计算字符数组长度
{
	int count = 0;
	while (*(++p) != '\0')  //从第一个位置开始
	{
		count++;
	}
	return count;
}

void getNext(char T[], int next[])
{
	next[1] = 0;        //从第一个位置开始
	int j = 1, k = 0;   //这里比较巧妙，先不用管什么意思，在相关的地方验证一下，然后就会明白了
	while (j < T[0])
	{
		if ((k == 0) || (T[j] == T[k]))
		{
			j++;
			k++;
			next[j] = k;
		}
		else
			k = next[k];  //往前找
	}
}

#include<iostream>
using namespace std;
#define STR_LEN 52
int main(int argc, char* argv[])
{
	int i = 1, j = 1;
	char S[STR_LEN], T[STR_LEN];
	int next[STR_LEN];
	cout << "输入源字符串：" << endl;
	cin >> S + 1;   //第0个位置用于存储长度
	cout << "输入目标字符串：" << endl;
	cin >> T + 1;
	T[0] = calLen(T);
	S[0] = calLen(S);
	if (T[0] > S[0] || T[0] == 0 || S[0] == 0)
	{
		cout << "字符串格式输入错误！" << endl;
		system("pause");
		return 0;
	}

	getNext(T, next);

	while (S[i] && T[j])  //判断字符串是否结束
	{
		if (S[i] == T[j])
		{
			i++;
			j++;
		}
		else   //将T向右滑动
		{
			j = next[j];  //将计算出来的k赋值给j
			if (j == 0)   //如果j==0，表明刚刚在j==1处（即一开始）两个字符串就不相等，那么S中的i要往右移动一位
			{             
				i++;
				j++;
			}
		}
	}
	if (T[j] == '\0')
		cout << "找到目标子串，从S中的第" << i - T[0] << "个位置开始！" << endl;
	else
		cout << "没有匹配的目标子串！" << endl;

	system("pause");
	return 0;
}

参考文献：

1、算法设计与分析-王红梅