KMP算法详解

lidki 5年前

字符串模式匹配我们相信大家都有遇过,然而我们也习惯用简单匹配法(即Brute-Force算法),其基本思路就是一个个逐一对比下去,这也是我们大家熟知的方法,然而这种算法的效率并不高,但利于理解。

假设主串s="ababcabcacbab",模式串为t="abcac",我们用肉眼很容易看出匹配位置为是s[5]--s[10];利用简单匹配算法代码如下:

int BF(string s,string t)//Brute-Force,简单匹配算法  {   int origin=-1;//模式匹配的起始位置   for(int i=0;i<s.size();i++)   {    int k;    for(k=0;k<t.size();k++)    {     if(s[i+k]!=t[k])        break;    }    if(k==t.size())//匹配成功    {     origin=i;     break;    }   }   return origin;//返回匹配成功的位置,若为-1,则匹配失败  }

然后这种算法效率显而易见效率并不高,其中包含了过多的不必要操作,并不能很好地达到实际工作中需要的效率。这种算法在最好的情况下时间复杂度为O(m),在最坏的情况下时间复杂度为M(nm)。

KMP算法

KMP算法较Brute-Force算法有较大的改进,主要消除了主串指针的回溯,从而是算法的效率有了某种程度的提高。

为了消除主串的指针回溯,需要分析模式串t,我们利用next[]数组来记录存放这些“部分匹配信息”。

next[]计算规则如下:

1)next[j]=-1; j=0;

2) next[j]=max(k); 0<k<j,p[0....k-1]=p[j-k...j-1];

3) next[j]=0; 其他条件

例如:计算ababa的next[]数组值

按照上面的规则我们可以填写出下表的next[]数组

p a b a b a
j 0 1 2 3 4
next[j] -1 0 0 1 2

根据上面规则,当j=0,next[j]=-1,所以第一个a的next值为-1;

当j=1时,0<k<j这样的k不存在,所以属于其他条件,即为0;

当j=4时,0<k<j,这样的k=1,2,3,因为要求最大的K,即从大到小验证k是否满足p[0....k-1]=p[j-k...j-1],若一个都不满足,属于其他条件,即为0,

当k=3时,str1=p[0....k-1]=aba,str2=p[j-k...j-1]=bab,str1!=str2,所以k!=3;

当k=2时,str1=p[0....k-1]=ab,str2=p[j-k...j-1]=ab,str1==str2,满足条件,所以k=2;

根据上面的条件,可以轻易写出next的计算函数;

//计算next数组,t为计算字符串  void calculateNext(int * & next,string t)  {   for(int j=0;j<t.size();j++)   {    bool state=true;//是否是等于0的情况    if(j==0)     *next=-1;    else     {     int k=j-1;//0<k<j,获取最大的k     while(k>0)     {      string str1="",str2="";      for(int i=0;i<=k-1;i++)      {       str1=str1+t[i];       str2=str2+t[j-k+i];      }      if(str1==str2)//若,p[0....k-1]=p[j-k...j-1];      {        *(next+j)=k;       state=false;//不是等于0的情况       break;      }      k--;           }     if(state)//满足其他条件,即为0 *(next+j)=0;    }     }  }

计算出匹配信息next后,我们就可以进行KMP匹配了,

主要思路是:

假设i和j分别为指示主串和模式串中正在比较的字符的当前位置,并对i 和j 赋初值0。  在匹配的过程中,若si=tj,则i和j分别增加1,继续进行比较。  否则,若j=0,si!=tj,则从s的下一个字符开始,即i增加一,若j!=0,令j=next[j]

理解了上面的思路,就很容易编写出KMP匹配代码:

//kmp匹配算法,s为主串,t为模式串  int KMP(int * next,string s,string t)  {   int j=0,i=0;//i为主串s正在匹配的字符,j为t正在匹配的字符      while(i<s.size()&&j<t.size())      {          if(t[j] == s[i])          {              j++;i++;          }          else          {              if(j==0)               {                  i++;//若第一个字符就匹配失败,则从s的下一个字符开始              }              else              {                        j = *(next+j);//,也可以j=next[j],用next确定t应回溯到的字符              }          }      }      if(j < t.size())//整个过程匹配失败      {          return -1;      }      return i-t.size();//匹配成功   //第二种写法   /*2. while(i < s.size())             {                      while(j > -1 && t[j] != s[i])                              j = next[j];                      i++, j++;                      if(j >= t.size()) return i - j;             }      return -1;  */         }

至此,我们就完成了KMP算法的学习。在学习KMP过程中,我发了一篇“另一种”有关的KMP算法,更好理解学习,附上链接:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

本次KMP的源代码地址:https://github.com/longpo/algorithm


来自:http://hm4123660.iteye.com/blog/2194569