KMP算法

Source

BF算法性能比较低,特别是在每趟匹配不成功时存在大量回溯,没有利用部分已经匹配成功的结果

KMP算法:与BF算法不同,会舍弃重复比较的过程

BF算法

在这里插入图片描述

Next数组:用来记录每一次j的滑动到哪一个位置

在这里插入图片描述
下面就是重复上面的重复行为,如果对当前i和j位置进行比较发生了失配,那么i不变,j去找到在next数组中对应当前位置的值,然后把j移动到该位置,再把j当前指向位置与i指向位置进行比较

next数组值推导及代码实现

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

KMP算法伪代码描述

在这里插入图片描述
在这里插入图片描述

next数组的求值

#include<iostream>
using namespace std;
#include<string>
//KMP
//1.求出T字符串每一个字符对应的next值,然后存放到next数组中
void get_next(string& T, int next[])
{
    
      
	int i = -1;//指向第一个前缀字符的位置
	int j = 0;//指向第一个后缀字符的位置

	next[0] = -1;//子串T中第一个字符的对应next值为-1
	//当j移动到next数组最后一个下一个元素的时候结束循环
	int num = T.length();
	cout << "num=" <<num<< endl;
	while (j < num-1)//下标从0开始,这里要是当前字符串长度-1
	{
    
      
		if (i == -1 || T[i] == T[j])//每次比较一个前缀和一个后缀
		{
    
      
			i++;
			j++;
			next[j] = i;
		}
		//如果失配
		else {
    
      
			//i回溯到当前next值的位置
			i = next[i];
		}
	}

}
//返回子串T在s串中开始位置下标
void KMP( string& T)
{
    
      
	int next[6];
	get_next(T, next);
	for (int i = 0; i <6; i++)
	cout << next[i] << endl;

}
//测试代码--------------
void test()
{
    
      
	//string s = "abcababxxabcabx";
	string T = "abcabx";
	//在a串中找出b串的起始位置,并返回
	KMP( T);
}
int main()
{
    
      
	test();
	system("pause");
	return 0;
}

在这里插入图片描述

KMP算法完整代码

#include<iostream>
using namespace std;
#include<string>
//KMP
//1.求出T字符串每一个字符对应的next值,然后存放到next数组中
void get_next(string& T, int next[])
{
    
      
	int i = -1;//指向第一个前缀字符的位置
	int j = 0;//指向第一个后缀字符的位置

	next[0] = -1;//子串T中第一个字符的对应next值为-1
	//当j移动到next数组最后一个下一个元素的时候结束循环
	int num = T.length();
	cout << "num=" <<num<< endl;
	while (j < num-1)//下标从0开始,这里要是当前字符串长度-1
	{
    
      
		if (i == -1 || T[i] == T[j])//每次比较一个前缀和一个后缀
		{
    
      
			i++;
			j++;
			next[j] = i;
		}
		//如果失配
		else {
    
      
			//i回溯到当前next值的位置
			i = next[i];
		}
	}

}
//返回子串T在s串中开始位置下标
int KMP( string& s,string& T,int next[])
{
    
      
	int i = 0;//指向s主串
	int j = 0;//指向T子串
	int sNum = s.length();
	int Tnum = T.length();
	while (i <=sNum - 1 && j <=Tnum - 1)
	{
    
      
		//第一次让j==0作为条件是因为,要把前缀和后缀更新出来
		//一开始j==-1,如果没有该条件,一开始就会进入j=next[-1]必然报错
		if (j==0||s[i] == T[j])
		{
    
      
			i++;
			j++;
		}
		else{
    
      
			//回退到当前j位置对应的next值,i位置不变
			j = next[j];
		}
	}
	cout << "循环结束后i=" << i << endl;
	cout << "循环结束后j=" << j << endl;
	//判断匹配是否成功
	if (i == sNum)//这里等于sNum是因为最后还有一次i++,因为只有i的值大于sNum-1才会退出循环
	{
    
      
		return i - j;
	}
	return -1;

}
//测试代码--------------
void test()
{
    
      
	int next[6];
	string s = "abcababxxabcabx";
	string T = "abcabx";
	//在a串中找出b串的起始位置,并返回
	get_next(T,next);
	int ret=KMP(s,T,next);
	cout << "子串T在主串s中的起始位置为:" << ret << endl;
}
int main()
{
    
      
	test();
	system("pause");
	return 0;
}

在这里插入图片描述