欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-06 22:35:45
...

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

一般的蛮力法如下:

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

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

1、理论

思想:尽量利用已经部分匹配的结果信息,尽量让 i 不回溯,加快模式串T的滑动速度。
先举个启发性的例子,然后引出理论。例子:
字符串匹配问题——KMP算法
字符串匹配问题——KMP算法

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

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

1.1、模式串T中的信息

抓住部分匹配时的两个特征:
字符串匹配问题——KMP算法
如上图所示,假设S[i]和T[j]不相等后,从T的第k个位置开始和S中的第i个位置比较,那么:
(1)从图的后半部分可得:
字符串匹配问题——KMP算法                                                                                (1)
(2)从图的后前部分可得: 
   字符串匹配问题——KMP算法                                                                                             (2)
所以,两式联立可得:
字符串匹配问题——KMP算法                                              (3)
所以,由上面的推理可知,只要提前知道模式串T本身的结构信息,就可以由j计算出k,即下一回T的匹配起点。另外,(3)式可能存在多种不同长度的首尾相等的可能,那么在这样的情况下,肯定是k越大越好,这样一方面可以减少再次匹配的字符数量;另一方面,T向右移动的位置相当S而言也是最慢的,这样也不会错过各种匹配的情况。比如:
字符串匹配问题——KMP算法

令k = next[ j ],则:
字符串匹配问题——KMP算法
计算next[j]的方法:
由模式T的前缀函数定义易知,next[1]=0,假设已经计算出next[1],next[2],…,next[j],如何计算next[j+1]呢?设k=next[j],则已有:
字符串匹配问题——KMP算法                                                         (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、算法设计与分析-王红梅