BF算法性能比较低,特别是在每趟匹配不成功时存在大量回溯,没有利用部分已经匹配成功的结果
KMP算法:与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;
}