首页 > 代码库 > kmp算法

kmp算法

前面说完KMP算法的特征向量,现在开始谈一下KMP算法了。

kmp算法的思想是这样的:

子串和长串比较,,当遇到相同的时候,继续比较,当不匹配时,子串右移,使得子串的不匹配位置的最长前缀串移动到长串的不匹配位置左边,与之相邻。

之后继续,如若一直不匹配,直到最长前缀串为0,则从子串第一位继续与不匹配位置比较。以此类推。直到子串的匹配位置达到它的长度。

这里有两个关键的变量,i,j,i是长串的游标,j是子串的游标。i只会增加,不会减少,j可增可减,而结束比较有两个条件,直到I=S。size也找不到,一个是J=P.size,找到位置。

 

int KMP_FindPat(String S, String P, int *N, int startindex) {
      //假定事先已经计算出P的特征数组N,作为输入参数
      // S末尾再倒数一个模板长度位置
      int LastIndex = S.size - P.size;
      //startindex过大,匹配无法成功
      if (LastIndex < startindex)
          return (-1);    
      int i;              
      int j = 0;           
      // i 是指向S内部字符的游标, j 是指向P内部字符的游标

         for (i = startindex; i < S.size; i++) { 
         //若当前位置的字符不同,则用特征数N求当前的j,
         //用于将P的恰当位置与S的i位置对准
             while (S.str[i] != P.str[j] &&  j > 0)    
          j = N[j-1];
             //P[j]与S[i]相同,继续下一步循环
             if (S.str[i] == P.str[j] ) j++;
             //匹配成功,返回该S子串的开始位置
             if ( j == P.size) 
                 return (i - j +1);
         };
     return (-1);   //P和S整个匹配失败,函数返回值为负
}

kmp算法