数据结构与算法5

串的模式匹配算法

子串（模式串）的定位操作通常称为串的模式匹配。

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。

串的顺序存储实现

#include<stdio.h>

#include<string.h>

#define MaxLen 256  /*定义能处理的最大的串长度*/

typedef struct {

    char str[MaxLen];

    int  curlen;  /*定义当前实际串长度*/

}SString;

BF算法设计思想：

将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。
直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0

int Index(SString *s,SString *t)

{ * 返回子串t在主串s中的位置。若不存在，则函数值为-*/

   int i,j;  i=; j=;

   while(i<s->curlen &&j<t->curlen) {

       if(s->str[i]==t->str[j])

       {  i++; j++;  }

       else /* 指针后退重新开始匹配 */

       {  i=i-j+; j=;  }

     }

     if(j>=t->curlen)

         return i-t->curlen+;

     else

         return -;

}

若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为：

最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次.

但一般情况下BF算法的时间复杂度为O(n+m)

模式匹配的一种改进算法——KMP

KMP算法的基本思想：每一趟匹配完成后，利用上一趟匹配的结果，将模式向右滑动尽可能远的一段距离。

其方法是：不回溯指针i，找出主串中第i个字符应和模式串的第几个字符比较。

显然next[j]只与模式串有关，与主串无关

KMP算法实现

int Index_KMP(SString *s, SString *t)

{

   int next[],i=,j=,v;

   getnext(t,next);/*先求得模式串的next函数值*/

   while(i<s->curlen && j<t->curlen){

      if(j==- || s->str[i]==t->str[j])

      { i++; j++;}

      else j=next[j]; /*i不变，j回退*/

   }

   if(j>=t->curlen)

       v=i-t->curlen+; /*匹配成功*/

   else

       v=-;   /*匹配失败*/

   return v;

}

求next:

void getnext(SString *t, int *next)

{  /*串t即作为目标串又作为模式串*/

    int j,k;

    j=;k=-;next[]=-;

    while(j<t->curlen-)  {

       if(k==-||t->str[j]==t->str[k]) {

          j++;k++;

          if(t->str[j]!=t->str[k])

              next[j]=k;

          else

              next[j]=next[k];

       }

       else k=next[k];

    }

}

推荐参考：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

Boyer-Moore 字符串匹配算法
https://www.cnblogs.com/gaochundong/p/boyer_moore_string_matching_algorithm.html

巴特西

数据结构与算法5—KMP算法

最新文章

热门文章