数据结构 第8讲 KMP算法
讲这个算法之前,我们首先了解几个概念:
串:又称字符串,是由零个或多个字符组成的有限序列。如S="abcdef"
子串:串中任意个连续的字符组成的子序列,称为该串的子串,原串称为子串的主串。如T="cde",T是S的子串。子串在主串中的位置,用子串的第一个字符在主串中出现的位置表示。T在S中的位置为3。
模式匹配:子串的定位运算称为串的模式匹配或串匹配。
假设有两个串S,T,设S为主串,也称正文串,T为子串,也称为模式,在主串S中查找与模式T相匹配的子串,如果查找成功,返回匹配的子串第一个字符在主串中的位置。
最笨的办法就是穷举所有S的所有子串,判断是否与T匹配。
例如:S="abaabaabeca",T=" abaabe",求子串T在主串S中的位置。
从S串第1个字符开始:i=1,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第2步;
从S串第2个字符开始:即i退回到i-j+2的位置,即i=2,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第3步;
从S串第3个字符开始:即i退回到i-j+2的位置,即i=3,j=1,比较两个字符是否相等,如果相等,则i++,j++;如果不等则执行第4步;
从S串第4个字符开始:即i退回到i-j+2的位置,即i=4,j=1,比较两个字符是否相等,如果相等,则i++,j++;此时T串比较完了,执行第5步;
需要返回子串在主串S中第一个字符出现的位置,即i-m=10-6=4,m为T串的长度。
上述算法称为BF(Brute Force)算法,Brute Force的意思是蛮力,暴力穷举。其时间复杂度最坏达到O(n*m),n,m分别为S、T串的长度。
实际上,完全没必要从S的每一个字符开始,暴力穷举每一种情况,Knuth、Morris和Pratt对该算法进行了改进,称为KMP算法。
我们再回头看刚才的例子:
从S串第1个字符开始:i=1,j=1,比较两个字符是否相等,如果相等,则i++,j++;按照BP算法,如果不等则i退回到i-j+2的位置,即i=2,j=1。
其实i不用回退,让j回退到第3个位置,接着比较即可。
是不是像T串向右滑动了一段距离?
为什么可以这样?为什么让j回退到第3个位置?而不是第2个?第四个?
因为T串中开头的两个字符和i指向的字符前面的两个字符一模一样噢,那j就可以回退到第3个位置继续比较了,因为前面两个字符已经相等了。
那我们怎么知道T串中开头的两个字符和i指向的字符前面的两个字符一模一样?难道还要比较?我们发现i指向的字符前面的两个字符和T串中j指向的字符前面两个字符一模一样,因为它们一直相等,才会i++,j++走到后面的位置。
也就是说,我们不必判断T串中开头的两个字母和i指向的字符前面的两个字符是否一样,只需要在T串本身比较就可以了。即T′的前缀和T′的后缀比较即可:
判断T′="abaab"的前缀和后缀是否相等,找相等前缀后缀的最大长度。
长度为1的:前缀"a",后缀:"b",不等×
长度为2的:前缀"ab",后缀:"ab",相等√
长度为3的:前缀"aba",后缀:"aab",不等×
长度为4的:前缀"abaa",后缀:"baab",不等×
注意:前缀和后缀不可以取字符串本身。串的长度为5,前缀和后缀长度最多达到4。
相等前缀后缀的最大长度为l=2,则j就可以回退到第l+1=3个位置继续比较了。
现在我们可以写出通用公式,next[j]表示j可以回退的位置,T′="t1t2…tj-1",则:
那么我们很容易求出T="abaabe"的next[]数组:
解释:
j=1:根据公式next[1]=0;
j=2:T′="a",没有前缀和后缀,next[2]=1;
j=3:T′="ab",前缀为"a",后缀为"b",不等,next[3]=1;
j=4:T′="aba",前缀为"a",后缀为"a",相等且l=1;前缀为"ab",后缀为"ba",不等,next[4]=l+1=2;
j=5:T′="abaa",前缀为"a",后缀为"a",相等且l=1;前缀为"ab",后缀为"aa",不等;前缀为"aba",后缀为"baa",不等,因此next[5]=l+1=2;
j=6:T′="abaab",前缀为"a",后缀为"b",不等;前缀为"ab",后缀为"ab",相等且l=2;前缀为"aba",后缀为"aab",不等;前缀为"abaa",后缀为"baab",不等,取最大长度2,因此next[6]=l+1=3。
这样找所有的前缀和后缀比较,是不是也是暴力穷举?
那怎么办呢?Look……
用动态规划递推一下:
首先大胆假设,我们已经知道了next[j]=k,即:
那么next[j+1]=?
考察以下两种情况:
tk=tj:那么next[j+1]=k+1,即相等前缀和后缀的长度比next[j]多1。
tk≠tj:当两者不相等时,我们又开始了这两个串的模式匹配,找next[k]的位置tk′与tj比较,程序中的处理,只需要把next[k]赋值给k,即k←next[k],然后再比较tk与tj是否相等,如果相等则next[j+1]=k+1;
如果不相等,则继续向前找next[k′],如果不相等,继续向前找,直到找到next[1]=0,停止,此时next[j+1]=0+1=1,即从第一个字符开始。
求解next[]的代码实现如下:
void get_next(SString T, int next[]) //求模式串T的next函数值
{
int j=1, k= 0;
next[1] = 0;
while (j
if (k== 0 || T[j] ==T[k])
next[++j]=++k;
else
k= next[k];
}
用上述方法再次求解求出T="abaabe"的next[]数组:
解释:
1.初始化时next[1]=0,j=1,k=0,进入循环,判断满足k==0,则执行next[++j]=++k,即next[2]=1,此时j=2,k=1;
2.进入循环,判断满足T[j]==T[k],T[2]≠T[1],则执行k=next[k],即k=next[1]=0,此时j=2,k=0;
3.进入循环,判断满足k==0,则执行next[++j]=++k,即next[3]=1,此时j=3,k=1;
4.进入循环,判断满足T[j]==T[k],T[3]=T[1],则执行next[++j]=++k,即next[4]=2,此时j=4,k=2;
5.进入循环,判断满足T[j]==T[k],T[4]≠T[2],则执行k=next[k],即k=next[2]=1,此时j=4,k=1;
6.进入循环,判断满足T[j]==T[k],T[4]=T[1],则执行next[++j]=++k,即next[5]=2,此时j=5,k=2;
7.进入循环,判断满足T[j]==T[k],T[5]=T[2],则执行next[++j]=++k,即next[6]=3,此时j=6,k=3;
8.j=T[0],循环结束。
结果是不是和穷举前缀后缀一模一样?
有了next[]数组,就很容易进行模式匹配了,当S[i]≠T[j]时,j退回到next[j]的位置继续比较即可。
这样求解非常方便,迅速,但是也发现有一个问题:当S[i]≠T[j]时,j退回到next[j],然后S[i]与T[k]比较。这样的确没错,但是如果T[k]=T[j],这次比较就没必要了,因为我们刚知道S[i]≠T[j]啊,那么肯定S[i]≠T[k],完全没必要再比了。
再向前找下一个next[],即找next[k]的位置,继续比较就可以了。本来应该和第k个位置比较呢,相当于跳到了k的下一个位置。减少了一次无效比较。
修改程序:
求解next[]的改进代码实现如下:
void get_next2(SString T, int next[]) //求模式串T的next函数值
{
int j=1, k= 0;
next[1] = 0;
while (j
{
if(k==0||T[j]==T[k])
{
j++;
k++;
if(T[j]==T[k])
next[j]=next[k]; //调到k的下一个位置,即next[k]
else
next[j]=k;
}
else
k=next[k];
}
完美~~~
/***KMP及改进算法***/
#include
#include
using namespace std;
#define Maxsize 100
typedef char SString[Maxsize+1]; //0号单元存放串的长度
bool StrAssign(SString &T, char *chars)//生成一个其值等于chars的串T
{
int i;
if (strlen(chars)>Maxsize)
return false;
else
{
T[0]=strlen(chars);
for(i=1; i<=T[0]; i++)
{
T[i]=*(chars+i-1);
cout<
}
cout<
return true;
}
}
void get_next(SString T, int next[])//计算next函数值
{
int j=1,k=0;
next[1]=0;
while(j
{
if(k==0||T[j]==T[k])
next[++j]=++k;
else
k=next[k];
}
cout<<"-----next[]-------"<
for(j=1;j<=T[0];j++)
cout<
cout<
}
void get_next2(SString T, int next[])//计算next函数值改进算法
{
int j=1,k=0;
next[1]=0;
while(j
{
if(k==0||T[j]==T[k])
{
j++;
k++;
if(T[j]==T[k])
next[j]=next[k];
else
next[j]=k;
}
else
k=next[k];
}
cout<<"-----next[]-------"<
for(j=1;j<=T[0];j++)
cout<
cout<
}
int Index_KMP(SString S, SString T, int pos, int next[])//KMP算法
{ //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
//其中,T非空,1≤pos≤StrLength(S)
int i=pos, j=1,sum=0;
while (i<=S[0] && j<=T[0])
{
sum++;
if (j==0||S[i]==T[j]) //继续比较后面的字符
{
i++;
j++;
}
else
j=next[j]; //模式串向右移动
}
cout<<"一共比较了"<
if (j>T[0]) //匹配成功
return i-T[0];
else
return 0;
}
int main()
{
SString S,T;
cout<<"串S:"<<" ";
StrAssign(S,"aabaaabaaaabea");
cout<<"串T:"<<" ";
StrAssign(T,"aaaab");
int *p=new int[T[0]+1]; //生成T的next数组
cout<
cout<<"KMP算法运行结果:"<
get_next(T,p);
cout<<"主串和子串在第"<
cout<
cout<<"改进的KMP算法运行结果:"<
get_next2(T,p);
cout<<"主串和子串在第"<
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。博客原文地址http://blog.csdn.net/rainchxy/article/details/78130155