lzh

刘政
posts - 17, comments - 1, trackbacks - 0, articles - 1

KMP算法(字符串模式匹配)

Posted on 2010-11-12 10:29 lzh525 阅读(1047) 评论(0)  编辑 收藏 引用 所属分类: 数据结构及算法问题
KMP算法是一种高效的模式匹配算法,复杂度可以达到O(m+n),而普通模式匹配算法的复杂度为O(m*n)。

普通模式匹配算法

  从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比较,若相等,则继续比较后面的字符。若不相等,则从主串本次开始比较的字符的下一个字符开始,与子串的第一个字符进行比较(即主串需要回退到本次比较开始字符的下一字符,模式串回退到首字符,主串与子串都需要回退)。
  匹配成功的标志:比较到子串的’\0’
  匹配失败的标志:比较到主串的’\0’,且此时子串的比较位不等于’\0’。
  算法复杂度:O(m*n)

KMP算法

KMP算法的改进思路
  在普通匹配算法中子串与模式串都需要回溯,但这些回溯不是必要的。因为当某一位发生失配时,可以根据已匹配的结果进行判断。该算法问题可以理解为,当模式串中的第k位与主串的第i位比较时发生不匹配时,需要将模式串向右滑动到哪里继续与主串的第i位进行比较?避免了不必要的主串回溯,减少了模式串回溯的位数,从而使算法复杂度提升到O(m+n)。

KMP算法的实现思路
  从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比较,若相等,则继续比较后面的字符。若不相等,则将模式串右移至合适的位置,找出模式串中合适的第k位与主串中发生不等的位进行对齐比较。算法继续。
  模式串与主串对齐继续比较的第k位必须满足其前k-1位与主串发生失配位置的前k-1位匹配,且该k-1位字串必须是最长的字串(即不存在k’>k,使模式串中的前k’-1位与主串发生失配位置的前k’-1位匹配,这是为了保证不漏过可以匹配的串)。
  该算法中的主程序同普通的匹配算法类似,区别在于当发生不匹配时,主串指针不需要回退(不动),将模式串右移到合适的位置继续进行比较。当模式串移动到第一位(下标为0)仍然不等时,主串指针右移一位。该算法的关键是模式串next[]的取得。
  匹配成功的标志:比较到子串的’\0’
  匹配失败的标志:比较到主串的’\0’,且此时子串的比较位不等于’\0’。

next[]数组的获得
  next[]数组记录了当模式串第j位发生失配时,模式串需要移动到第k位,使第k位与主串发生失配的位对齐继续比较(next[j]=k)。next[]数组使用递推实现,假设next[j]=k已经获得,则从next[j]开始推next[j+1]。具体算法如下。
  假设next[j]=k(第j位及之前的next[]值已经求得,k<j),当模式串第j位发生失配时,模式串需要移动到第k位,使第k位与主串发生失配的位对齐继续比较。这说明:除了第k位,其前面的k-1位与主串发生失培的前k-1位已经匹配。(因为当第p[k]位失配时,p[1]p[2]…p[k-1]已经等于s[i-k+1]s[i-k+2]…s[i-1])
  而同时由于:p[j-k+1]p[j-k+2]…p[j-1]=s[i-k+1]s[i-k+2]…s[i-1]
  所以:p[1]p[2]…p[k-1]= p[j-k+1]p[j-k+2]…p[j-1]

情况1:
  若p[k]=p[j],即p[next[j]]=p[j],那么:p[1]p[2]…p[k-1]p[k]= p[j-k+1]p[j-k+2]…p[j-1]p[j],则根据定义:next[j+1]=k+1=next[j]+1

情况2:
  若p[k]!=p[j],即p[1]p[2]…p[k-1]p[k]!= p[j-k+1]p[j-k+2]…p[j-1]p[j],即p[k]与p[j]发生不等。把p[k]为模式串,即模式串第k位发生失配,根据KMP算法的基本思路,当模式串第k位发生失配时,模式串应移动到第next[k]=k’位与主串进行比较。此时:p[1]p[2]…p[k’-1]= p[j-k’+1]p[j-k’+2]…p[j-1]。然后再比较p[k’]与p[j],若相等,同情况1:next[j+1]=k’+1= next[k]+1;若不相等,返回到情况2的头进行比较。(两种判断均可以归入情况1或者情况2,所以可以进行循环)

情况3:
  若next[k]=-1,即发生失配元素的前一个元素与第一个元素a[0]仍然不等,该应使该失配元素直接与第一个元素比较,next[j+1]=0。(该情况可与第一种情况合并(因为next[0]=-1))

简单得说:
  从next[j]=k开始比较,首先将k与自身对齐比较(找可以与j对齐比较的最长子串),如果相等,则p[k]=p[j],满足情况1。若不相同,即模式串第k位发生失配,移动到k'=next[k]位继续进行比较。返回情况1或者2。如果next[k]=-1(仅第1位的next[0]的值为-1),说明j+1的前一位j与第一位比较仍然不等,那应该让第j+1位直接与第1位(下标为0)进行比较。
  next[k+1]的计算依赖于next[k],next[k+1]仅有一种方式获得,即第k+1字符的前面k个字符完全匹配(或者前一元素与第一个元素仍然不匹配)。而next[k]是已经计算的,即next[k]可以保证第k字符的前面k-1个字符(除了第k个字符)完全匹配,而且该字串是最长字串。因为只需比较第k个字符是否匹配。匹配成功即情况一,匹配失败则继续寻找next[next[k]]。
  编程时,每次进行计算next[j+1]时,必须保证j与k呈对应关系,即每新一次计算前,next[j]=k(next[j+1]=k+1,因而也可以写成next[++j]=++k)。

KMP算法的再改进

  当第k+1位发生失配时,根据原算法,可以找到一个子串,与之匹配。此时,next[j+1]=k+1
但若 T[j+1]= T[next[j+1]]=T[k+1],则当T[j+1]发生失配时,程序会使回到第next[j+1](=k+1)位,与T[j+1]所对应的主串字符进行比较。但由于主串字符已经不等于T[j+1],因而也必然不等于T[next[j+1]],因而此次比较必然失败。
  改进:当T[j+1]= T[next[j+1]]=T[k+1]时,next[j+1]= next[next[j+1]]=next[k+1],从而避免不必要的重复比较。

附:
普通模式匹配算法代码:
int mystrstr(char* S, char* T, int pos)
{
    int i=pos; //设置主串的指针位置(初始位置为给定的开始位置)
    int j=0; //设置子串的指针位置(初始位置为子串的首元素)
    
    while (S[i]!='\0')
    {
          if (T[j]=='\0') {return (i-j+1);} //比较到子串的’\0’,匹配成功
          if (S[i]==T[j]) {
             i++;
             j++;
            //子串与主串在该位的匹配值相等,则继续比较下一字符
          } else { //若不相同
            i=i-j+1; //主串回退到本次比较开始字符的下一字符 
            j=0; //模式串回退到首字符
          }
    }
    return 0; 比较到主串的’\0’,且此时子串的比较位不等于’\0’,匹配失败
}

KMP主程序代码:
int mystrstr(char* S, char* T, int pos, const int* next)
{
    int i=pos; //主串指针 
    int j=0; //模式串指针 
    
    while (S[i]!='\0') //当主串指针所指字符不为'\0'时,继续比较 
    {     
          
          if (j==-1) {i++;j++;}
          // 当头元素仍然不匹配时,j=-1,此时j指针清0指向模式串的首元素, i指针指下主串的下一元素 
          if (T[j]=='\0') {return (i-j+1);}
          // 当模式串指针所指元素为'\0'时,匹配完成,返回位置 
          if (S[i]==T[j]) {
             i++;
             j++;
             //当模式串指针与主串指针所指元素相同时,两指针都相加.比较下一元素 
          } else {
            j=next[j];
            //若模式串指针与主串指针所指内容不同时,模式串指针回退指到next[j]位置(第j位发生失配) 
          }
    }
    return 0;
}

生成next[]数组代码
//该程序用next[i]来推测next[i+1]
//每次比较开始时next[i]=k,每次比较开始前i与k成对应关系 
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1; //k为当第j位发生失配时,需要移动到的下一次进行比较的位(第k位)            
     next[0]=-1;
     //给定初始值,当比较到第一个元素(下标为0)仍然不等时,k的值为-1 
     
     while (j<strlen(T)) //j的大小有strlen(T)个,下标从0开始 
     {
           if (k==-1||T[k]==T[j])
           {
              //next[j]=k的定义为: t[0]...t[k-1]=t[j-k+1]...t[j-1] 
              //当T[k]=T[j]时,即T[next[j]]=T[j]时,T[1]...T[k]=T[j-k+1]...T[j],此时next[j+1]=next[j]+1=k+1,即可以求出next[j+1] 
              //当k=1时,即j+1的前一个元素与模式串的首元素相比,仍然不同,则应该让第j+1个元素直接与首元素进行比较 
              next[j+1]=k+1;
              j++; 
              k++; //k=next[j+1]=k+1,不能写k=next[j+1],因为上面一句j已经变化过了
              //next[j+1]=next[j]+1=k+1,即j+1与k+1是成对出现的 
              //下次比较开始前,j与k必须成对应关系出现, 满足这个式子:next[j+1]=k+1
           } else {
               k=next[k];
               //如果不等,可以理解为模式串的第k(next[j])位发生不匹配
               //则寻找到第next[k]位(保证k之前的元素匹配)继续进行比较
               }
     }
}

生成KMP改进算法的next[]数组代码
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1;

     next[0]=-1;
     // next[j]=k
     
     while (j<strlen(T))
     {
           if (k==-1||T[k]==T[j])
           {
              next[j+1]=k+1;
              
              if (T[j+1]==T[next[j+1]]) {
                 next[j+1]=next[next[j+1]];
              } 
              //就多了这段,当T[j+1]与T[next[j+1]]相等时,使next[j+1]=next[next[j+1]]
              j++;
              k++;
           } else {
               k=next[k];
               }
     }                 
}


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/ultrasurf/archive/2007/11/08/1873589.aspx

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理