本文主要是介绍kmp算法的基本总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
字符串的快速匹配kmp算法
1,朴素的模式匹配算法
目标串 T t0 t1 t2 t3 t4 t5 t6 t7 t8 t9……
模式串 pat p0 p1 p2 p3 p4 p5 p6 p7 p8 p9……
如果t0=p0,t1=p1,t2=p2 tm-1=pm-1,则字符串匹配成功,否则将pat串后移一位
形成
目标串 T t0 t1 t2 t3 t4 t5 t6 t7 t8 t9……
模式串 pat p0 p1 p2 p3 p4 p5 p6 p7 p8 p9……
再次进行匹配判断,失败再后移一位,如果tn-1和pm-1不相等,则匹配结束,返回不存在目标串中不含有字串
这种匹配算法是带回溯的算法,一旦比较不相等,就将模式串pat后移一位,从p0开始判断,设目标串的长度为n,匹配串的长度为m,第一趟失败比较m次,第二趟失败又比较m次,依次下去,最坏的情况是比较n-m+1次,在多数的情况下m是远小于n的,所以可以认为算法的时间复杂度是O(m*n)。由此我们引入一种不回溯的匹配算法,提高匹配的效率。
2改进的算法kmp算法
我们给出目标串味T abbaba,模式串为aba
根据朴素算法匹配为
T a b b a b a
P a b a
我们可以看到第一趟t0=p0,t1=p1,t2!=p2;但是p0!=t1;由此可以推断t1=p1!=p0,将P右移一位用t1和p0比较是肯定不相等的,没必要再进行了,p0=p2,所以同样p0!=t2;这一趟也不用比较,我们应该直接将P向右移动3位,直接用t3和p0进行比较,这样匹配就消除了回溯,这就是kmp算法的思想
一般情况 T=“t0t1t2t3t4……tn-1”,模式P="p0p1p2p3pn-1",根据1中的朴素匹配算法可以得到从目标串T的第s个位置ts与模式串的第0个位置进行比较,直到在目标T第s+j位置t(s+j)处失配
这是,可以得到 t(s)t(s+1)t(s+2)t(s+3)……t(s+j-1)=p0p1p2p3……p(j-1) (x)
那么下一趟应该从目标T中第(s+1)个位置开始匹配
若想成功则有,p0p1p2p3……P(m-1)=t(s+1)t(s+2)t(s+3)………t(s+m);
如果在模式串P中p0p1p2p3……p(j-2) != p1p2p3……p(j-1); (y)
则第s+1趟不用比较了
因为由xy式可以得到 p0p1p2p3……p(j-2) !=t(s+1)t(s+2)t(s+3)……t(s+j-1)
那么第s+2趟呢,
我们要判断一下p0p1p2……p(j-3)与p2p3……P(j-1)的关系。
如果p0p1p2……p(j-3) != p2p3……P(j-1)
仍有
p0p1p2p3……P(j-3) != t(s+2)t(s+3)……t(s+j-1)
这一趟没必要
我们以此类推直到有一个k使p0p1……p(k+1) != p(j-k-2)(j-k-1)……p(j-1)
p0p1……p(k) = p(j-k-1)(j0k)……p(j-1)
才有p0p1……p(k) = t(s+j-k-1)t(s+j-k)……t(s+j-1)
p(j-k-1) p(j-k) ……p(j-1)
这时模式串p已经向后滑动了j-k-1位,因此可以直接从t中的t(s+j)与模式中的p(k+1)开始,继续向下比较。
这个算法中,目标T在第s趟比较失配后,指针s不必回溯,算法下一趟从此开始向下进行比较,而在模式p中,扫描指针p应退回到p(k+1)处
对于不同的j值,k值只依赖与模式p本身的前j个字符的构成。因此我们可以用一个next数组来表示
设模式P=p0p1p2p3……pm-2pm-1,则next数组的取值如下
-1(j=0)时
next(j) = k+1当0<=k<j-1时,且使的p0p1……p(k)=p(j-k-1)p(j-k)……p(j-1)
0其它情况
p=abaabcac
j 0 1 2 3 4 5 6 7
p a b a a b c a c
next(j) -1 0 0 1 1 2 0 1
下面是用kmp算法实现的匹配代码
时间复杂度取决于while循环,因为无回溯,最多比较lent次,时间复杂度为O(lent)。
那么问题来了,我们如何得到next数组。
我们可以用递推的方法得到next数组;设next(j)=k;
则0<=k<j-1且p0p1……pk=p(j-k-1)p(j-k)……p(j-1)
若设next(j+1)=max{k+1|0《=k+1<j},使得p0p1……p(k=1)=p(j-k-1)p(j-k)……p(j)成立
若p(k+1)=p(j),next(j+1)=k+1=next(j)+1;
若p(k+1) != p(j),在p0p1p2……pk中存在p0p1……ph = p(k-h)p(k-h+1)……p(k);
1 存在h值
next(k)=h;
p0p1……ph = p(k-h)p(k-h+1)……p(k) = p(j-h-1)p(j-h)……p(j-1)
如果p(h+1)=p(j)
next(j+1)=h+1=next(k)+1=next(next(j))+1;
否则在p0p1……ph中寻找更小的值,next(h)=t;以此下去,直到next(t)=-1,失败
求next数组代码
时间复杂度为O(lenp);总的时间复杂度为O(lenp+lent).
参考数据结构书
目标串 T t0 t1 t2 t3 t4 t5 t6 t7 t8 t9……
模式串 pat p0 p1 p2 p3 p4 p5 p6 p7 p8 p9……
如果t0=p0,t1=p1,t2=p2 tm-1=pm-1,则字符串匹配成功,否则将pat串后移一位
形成
目标串 T t0 t1 t2 t3 t4 t5 t6 t7 t8 t9……
模式串 pat p0 p1 p2 p3 p4 p5 p6 p7 p8 p9……
再次进行匹配判断,失败再后移一位,如果tn-1和pm-1不相等,则匹配结束,返回不存在目标串中不含有字串
这种匹配算法是带回溯的算法,一旦比较不相等,就将模式串pat后移一位,从p0开始判断,设目标串的长度为n,匹配串的长度为m,第一趟失败比较m次,第二趟失败又比较m次,依次下去,最坏的情况是比较n-m+1次,在多数的情况下m是远小于n的,所以可以认为算法的时间复杂度是O(m*n)。由此我们引入一种不回溯的匹配算法,提高匹配的效率。
2改进的算法kmp算法
我们给出目标串味T abbaba,模式串为aba
根据朴素算法匹配为
T a b b a b a
P a b a
我们可以看到第一趟t0=p0,t1=p1,t2!=p2;但是p0!=t1;由此可以推断t1=p1!=p0,将P右移一位用t1和p0比较是肯定不相等的,没必要再进行了,p0=p2,所以同样p0!=t2;这一趟也不用比较,我们应该直接将P向右移动3位,直接用t3和p0进行比较,这样匹配就消除了回溯,这就是kmp算法的思想
一般情况 T=“t0t1t2t3t4……tn-1”,模式P="p0p1p2p3pn-1",根据1中的朴素匹配算法可以得到从目标串T的第s个位置ts与模式串的第0个位置进行比较,直到在目标T第s+j位置t(s+j)处失配
这是,可以得到 t(s)t(s+1)t(s+2)t(s+3)……t(s+j-1)=p0p1p2p3……p(j-1) (x)
那么下一趟应该从目标T中第(s+1)个位置开始匹配
若想成功则有,p0p1p2p3……P(m-1)=t(s+1)t(s+2)t(s+3)………t(s+m);
如果在模式串P中p0p1p2p3……p(j-2) != p1p2p3……p(j-1); (y)
则第s+1趟不用比较了
因为由xy式可以得到 p0p1p2p3……p(j-2) !=t(s+1)t(s+2)t(s+3)……t(s+j-1)
那么第s+2趟呢,
我们要判断一下p0p1p2……p(j-3)与p2p3……P(j-1)的关系。
如果p0p1p2……p(j-3) != p2p3……P(j-1)
仍有
p0p1p2p3……P(j-3) != t(s+2)t(s+3)……t(s+j-1)
这一趟没必要
我们以此类推直到有一个k使p0p1……p(k+1) != p(j-k-2)(j-k-1)……p(j-1)
p0p1……p(k) = p(j-k-1)(j0k)……p(j-1)
才有p0p1……p(k) = t(s+j-k-1)t(s+j-k)……t(s+j-1)
p(j-k-1) p(j-k) ……p(j-1)
这时模式串p已经向后滑动了j-k-1位,因此可以直接从t中的t(s+j)与模式中的p(k+1)开始,继续向下比较。
这个算法中,目标T在第s趟比较失配后,指针s不必回溯,算法下一趟从此开始向下进行比较,而在模式p中,扫描指针p应退回到p(k+1)处
对于不同的j值,k值只依赖与模式p本身的前j个字符的构成。因此我们可以用一个next数组来表示
设模式P=p0p1p2p3……pm-2pm-1,则next数组的取值如下
-1(j=0)时
next(j) = k+1当0<=k<j-1时,且使的p0p1……p(k)=p(j-k-1)p(j-k)……p(j-1)
0其它情况
p=abaabcac
j 0 1 2 3 4 5 6 7
p a b a a b c a c
next(j) -1 0 0 1 1 2 0 1
下面是用kmp算法实现的匹配代码
<span style="font-size:18px;">int fastfind(char *s,char *str,int next[])//s为目标串,str为匹配串
{
int p=0;
int t=-1;
int lent=strlnen(s);
int lenp=strlen(str);
while(p<lenp&&t<lent)
{
if(p==-1||str[p]==s[t])
{
p++;
t++;
}
else
{
p=next[p];
}
}
if(p<lenp)
return -1;//匹配失败
else
return t=lenp;//匹配成功
}</span>
时间复杂度取决于while循环,因为无回溯,最多比较lent次,时间复杂度为O(lent)。
那么问题来了,我们如何得到next数组。
我们可以用递推的方法得到next数组;设next(j)=k;
则0<=k<j-1且p0p1……pk=p(j-k-1)p(j-k)……p(j-1)
若设next(j+1)=max{k+1|0《=k+1<j},使得p0p1……p(k=1)=p(j-k-1)p(j-k)……p(j)成立
若p(k+1)=p(j),next(j+1)=k+1=next(j)+1;
若p(k+1) != p(j),在p0p1p2……pk中存在p0p1……ph = p(k-h)p(k-h+1)……p(k);
1 存在h值
next(k)=h;
p0p1……ph = p(k-h)p(k-h+1)……p(k) = p(j-h-1)p(j-h)……p(j-1)
如果p(h+1)=p(j)
next(j+1)=h+1=next(k)+1=next(next(j))+1;
否则在p0p1……ph中寻找更小的值,next(h)=t;以此下去,直到next(t)=-1,失败
求next数组代码
void getnext(int next[],char *str)
{
int j=0;
int k=-1;
int lenp=strlen(str);
next[0]=-1;
while(j<lenp)
{
if(k==-1||str[k]==str[j])
{
k++;
j++;
next[j]=k;
}
else
k=netx[k];
}
}
时间复杂度为O(lenp);总的时间复杂度为O(lenp+lent).
参考数据结构书
这篇关于kmp算法的基本总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!