串模式匹配之BF算法和KMP算法

时间:2020-12-28 09:54:22

在给定两个串S=“s1s2...sn”和T=“t1t2...tm”,在主串S中寻找子串T的过程称为模式匹配,T称为模式,如果匹配成功则返回T在S中第一次出现的位置,否则返回0.在数据结构中一般串的存储采用的顺序存储:

串模式匹配之BF算法和KMP算法

有两种算法来进行模式匹配:

1、朴素的模式匹配算法--BF算法

BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。

 举例说明:

    S:  ababcababa

    P:  ababa

  BF算法匹配的步骤如下

           i=0                                   i=1                             i=2                         i=3                          i=4

  第一趟:ababcababa         第二趟:ababcababa      第三趟:ababcababa    第四趟:ababcababa    第五趟:ababcababa

             ababa                            ababa                          ababa                        ababa                       ababa

            j=0                                   j=1                            j=2                         j=3                         j=4(i和j回溯)

 

              i=1                                 i=2                           i=3                            i=4                        i=3

 第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababcababa   第十趟:ababcababa

              ababa                              ababa                           ababa                        ababa                        ababa

             j=0                                  j=0                           j=1                           j=2(i和j回溯)            j=0

 

              i=4                                    i=5                          i=6                           i=7                          i=8

第十一趟:ababcababa       第十二趟:ababcababa    第十三趟:ababcababa   第十四趟:ababcababa   第十五趟:ababcababa

                     ababa                               ababa                           ababa                          ababa                          ababa

               j=0                                    j=0                         j=1                            j=2                         j=3

 

                    i=9

第十六趟:ababcababa

                       ababa

                    j=4(匹配成功)

代码如下:

int BF(char *S,char *T){
int i=0;
int j=0;
int s=strlen(S);
int t=strlen(T);
//设置开始匹配的起始小标
while(i<s&&j<t)//s,t存的是长度
{if(S[i]==T[j]){i++;j++;}
else {i=i-j+1;j=0;}
}
if(i>=t) return (i-j);
else return 0;}
对于其时间性能分析:

设串S长度m,串T长度为m,在匹配成功时候,考虑两种极端情况:

a:最好情况,每次匹配不成功发生在串T第一个字符。故在si处匹配成功时,前i-1次不成功匹配共比较(i-1)*1次,第i次匹配成功时比较了m次,故总共比较i-1+m次,其中0<i<n。所有匹配成功可能有n-1+m种。在等概率情况下,有:

串模式匹配之BF算法和KMP算法
其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。由此引入了KMP算法。

b:在最坏情况 下,每次匹配不成功发生在串T最后,则匹配成功在si处时候,在i-1次不成功匹配中比较了(i-1)*m,第i次比较m次,一共比较i*m次,类似可以求得时间性能O(n*m)

2、改进的模式匹配算法--KMP算法

2.1 KMP算法解析:

设目标串为s,模式串为t,如果按照上面的BP算法,会存在如下问题:当s[i]!=t[j]时,s需要移动到下一位,t需要从头开始,需要重复进行一系列不匹配的比较。

串模式匹配之BF算法和KMP算法

如图所示,模式串每从头开始,就要重复的进行"b不匹配,c不匹配,d不匹配",这种多次操作实际上是冗余的;另外我们注意到:在s[i]!=t[j]前,s与t对应位都是相同的,故看似是s与t的比较,实际上也是模式串t本身的比较。由此,如果模式串存在部分匹配情况,为了避免冗余的比较,我们先自身比较一次,保存结果下次直接使用,这种预处理结果就是所谓的模式值next数组。

next数组主要是进行最长首尾匹配。给定一个字符串N(长度为n,即N由N[0]...N[n]组成),找出是否存在这样的i,使得N[0]=N[n-i],N1=N[n-i-1],……,N[i]=N[n],不存在返回-1。如下图所示:

串模式匹配之BF算法和KMP算法

 图中绿色部分表示完全相等,满足首尾匹配。存在以下关系:

串模式匹配之BF算法和KMP算法
next(N[j])=e,则由首尾匹配准则N[0]-N[e]=N[j-e]-N[j],且有M[y-j]-M[j]=N[j-e]-N[j]=N[0]-N[e],故M[y-j]-M[j]=N[0]-N[e],则将模式串N移至首尾相等处,接下来只需看N(e+1)==M(y+1)?

首先我们假设N[j]已经求出了next(next(N[0...j]) = i),那么对于N[j+1]的next思想一般分以下情况:

   N[j+1]==N[i+1],next(N[0...j+1]) =i+1

  N[j+1]!=N[i+1],需要循环查找i的next,即k = next(N[0...i]),之后再用N[j+1]与N[k+1]比较,直到字符串长度为0或者其相等为止。

  串模式匹配之BF算法和KMP算法

假设上图中k = next(i),那么我们说如果N[k+1] == N[j+1],那么k+1就是最长的首尾匹配位置,即next(N[j+1]) = k+1。

2.2 KMP算法设计:

BF算法简单但是效率低下,由此改进算法是KMP算法,其基本思想是主串不再进行回溯,模式T向右滑动至某个位置k,使得tk对着si继续进行匹配,故问题关键是确定位置K。

模式中每一个字符tj都对应一个k,而这个K仅仅依赖于模式本身,与主串无关,用next[j]表示tj个元素对应的k(0<j<m)。

首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

如:- "A"的前缀和后缀都为空集,共有元素的长度为0;

- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

利用此思想可以得到一个部分匹配表:

串模式匹配之BF算法和KMP算法

由此可以得向右移动位数: 移动位数 = 已匹配的字符数 - 对应的部分匹配值,进而k值即可确定。

故第一部是求得某串T的部分匹配值数组next[j],即所有模式T的字符处前缀与后缀相同字符串长度的最大值构成的数组:

串模式匹配之BF算法和KMP算法

bool equals(char *p,int i,int j)     //判断p[0...j-1]与p[i-j...i-1]是否相等  
{
int k=0;
int s=i-j;
for(;k<=j-1&&s<=i-1;k++,s++)
{
if(p[k]!=p[s])
return false;
}
return true;
}
void getnext(char*T,int*next){int i,k,temp;for(i=0;i<strlen(T);i++){if(i==0)next[i]=0;else{temp=i-1;for(k=temp;k>=0;k--)if(equals(T,i+1,k)){next[i]=k;break;}}}}

改进的算法:

//KMP
void getnext(string t,int next[]){
int i,j;
j=0;
next[0]=-1;next[1]=0;
for(int k=1;k<t.length();k++)
{
while(j>0&&t[k]!=t[j])j=next[j];
if(t[k]==t[j])j++;
next[k+1]=j;
}
}

最后KMP函数调用:

int index_kmp(string s,string t,int next[]){
int i=0,j=0,k;
getnext(t,next);
while(i<s.length()&&j<t.length()){
if(j==-1||s[i]==t[j]){i++;j++;}//考虑j=-1
else j=next[j];
}
if(j>=t.length())return (i-j);
else return -1;
}

实现:

int main(){
char a[]="BBC ABCDAB ABCDABCDABDE";
char b[]="ABCDABD";
int next[100];
getnext(b,next);
cout<<"KMP: "<<KMP(a,b,next)<<endl;
cout<<"BF: "<<BF(a,b)<<endl;
system("pause");
return 0;}

参考:http://blog.csdn.net/yutianzuijin/article/details/11954939/