您的位置: 网站首页 > 程序开发 > 数据结构 > 第4章 串、数组和广义表 > 【4.3 串的模式匹配算法】

4.3 串的模式匹配算法

 

4.3  串的模式匹配算法

所谓串的模式匹配运算,就是判断某串是否为另一已知串的子串,如是其子串,则给出该子串的起始点(即从已知串的第几个字符开始)。所以此运算又称为子串的定位运算。串的模式匹配算法应用非常广泛,例如,在文本编辑程序中,常常需要查找某一特定单词在文本中出现的位置。

设已知串S和串T,要求判断串T是否是串S的子串,如果是其子串则给出起始点。显然串T是串S的子串的一个必要条件是,它的长度len (T)一定要小于或等于串S的长度len (S),即len (T)len (S)

4.3.1  求子串位置的定位函数Index (S, T, pos)

子串的定位操作通常称做串的模式匹配(其中T被称为模式串),是各种串处理系统中最重要的操作之一。采用串的定长顺序存储结构,可以写出不依赖于其他串操作的匹配算法,算法如下所示:

int Index(HString S,HString T,int pos)

{

    /*返回子串T在主串S中第pos个字符之后的位置。如不存在,则返回0*/  

    int i=pos,j=1;

    while(i<=S[0] && j<=T[0])

    {

        if(S[i]==T[j])

        {i++,j++;}

        else        

        {  

            i=i-j+2,j=1;

        }

    }

    if(j>T[0])

        return i-T[0];

    else return 0;

}

在上述算法的函数过程中,分别利用计数指针ij指示主串S和模式串T中当前正待比较的字符位置。算法的基本思想是:从主串S的第pos个字符起和模式的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式串的字符比较。依此类推,直至模式串T中的每个字符依次和主串S中的一个连续的字符序列相等,则称匹配成功,函数值为和模式串T中的第一个字符相等的字符在主串S中的序号;否则称匹配不成功,函数值为零。

例如,假设主串S为“ababcabcacbab”,模式串T为“abcac”,匹配过程如图4-3所示。

4-3  匹配过程

当开始将串T的第1个字符与串S的第1个字符比较,头两对字符均都匹配,但第3对字符为ac不匹配;第2轮将T的第1个字符与S的第2个字符比较,可以发现ab不匹配;第3轮再将T的第1个字符与S的第3个字符比较,前4对字符都匹配,第5对又不匹配;这样继续下去,直至进行到第6轮时才达到完全匹配,故返回子串在S中的起始位置为6

还存在一种称为首尾匹配的算法,先比较模式串的第1个字符,再比较模式串的最后一个字符,最后比较模式串中从第2个到第n-1个字符。

其算法描述如下:

int Index_FL(SString S, SString T, int pos)

{

   /*返回子串T在主串S中第pos个字符之后的位置*/

   /*若不存在,则函数值为0*/

   /*其中,T非空,1posStrLength(S)*/

   sLength=S[0];tLength=T[0];

   i=pos;

   patStartChar=T[1];

   patEndChar=T[tLength];

   while(i<=sLength–tLength+1)

   {

      if(S[i]!=patStartChar) ++i;            /*重新查找匹配起始点*/

      else if(S[i+tLength-1] != patEndChar)

        ++i;

      /*模式串的“尾字符”不匹配*/

      else

      {                                          /*检查中间字符的匹配情况*/

      k = 1;j = 2;

      while(j<tLength && S[i+k]=T[j])

         {++k;++j; }

         if(j==tLength)

         return i;

         else

         ++i;                                    /*重新开始下一次的匹配检测*/

      }

   }

   return 0;

}

4.3.2  模式匹配的一种改进算法

上小节两种算法的时间复杂度为O(m*n),其比较次数较大,原因在于目标串的检测指针需要回溯。本小节将要讨论的模式匹配的一种改进算法是由D.E.KnuthV.R.PrattJ.H.Morris同时发现的,因此人们称它为克努特—莫里斯—普拉特操作(简称为KMP算法)。此算法可以在O(m+n)的时间数量级上完成串的模式匹配操作,可使目标串的检测指针不必回溯。其改进在于:在发生失配时,主串不需要回溯,而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离,继续进行比较。这里要强调的是,模式串不一定向右移动一个字符的位置,右移也不一定必须从模式串起点处重新试匹配,即模式串一次可以右移多个字符的位置,右移后可以从模式串起点后的某处开始试匹配。

即当S[i]<>T[j]时,已经得到的结果:S[i..i+j-2]==T[1..j-1],若已知T[1..k-1]==T[j-k+ 1..j-1],则有S[i-k+1] == T[1..k-1]

可以定义模式串的next 函数,若定义next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需要重新和主串中该字符进行比较的字符的位置。模式串的next 函数的定义如下:

         0     j=1

next[j]=   Max{k|1<k<j'p[1]...p[k-1]' = 'p[j-k+1]...p[j-1]' }

         1     其他情况

这样在求得了模式的next 函数之后,可按如下的KMP算法进行匹配:

int Index_KMP(SString S, SString T, int pos)

{

   /* 利用模式串Tnext函数求T在主串S中第pos个位置*/

   /* 字符之后的位置的KMP算法。其中,T非空*/

   /* 1posStrLength(S) */

   i=pos;j=1;

   while(i<=S[0] && j<=T[0])

   {

      if(j==0 || S[i]==T[j]) {++i;++j;}

      /* 继续比较后继字符*/

      else j=next[j];                        /* 模式串向右移动*/

   }

   if(j>T[0])

      return i-T[0];                         /* 匹配成功*/

   else return 0;

}

现在的问题就是如何求得模式的next 函数,而求next函数值的过程实际上是一个递推过程,分析如下:

已知:next[1] = 0

假设:next[j] = k;又T[j] = T[k];

则:next[j+1] = k+1;

若:T[j]=T[k];

则需往前回溯,检查T[j] == T[];

这实际上也是一个匹配的过程,只是主串和模式串是同一个串。求模式串Tnext函数值的算法如下:

void get_next(SString &T,int &next[ ])

{

   /* 求模式串Tnext函数值并存入数组next*/

   i=1; next[1]=0;j=0;

   while (i < T[0])

   {

      if(j==0 || T[i]==T[j])

         { ++i; ++j;next[i]=j;}

      else j=next[j];

   }

}