欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

串的模式匹配算法理论与思想

程序员文章站 2022-07-15 08:50:53
...

 串的模式匹配算法

一、基本概念

1、模式匹配(定位)

设有主串S和子串T(将S称为目标串,将T称为模式串),在主串S中,从位置start开始查找,如若在主串S中找到一个与子串T相等的子串,则返回T的第一个字符在主串中的位置,否则返回-1

 

2、算法目的

          确定主串中所含子串第一次出现的位置(定位)

 

3、算法种类

     BF算法  (又称古典的、经典的、朴素的、穷举的)

 

          KMP算法

1Brute-Force算法的设计思想:

         将主串S的第一个字符和模式T的第1个字符比较,

    若相等,继续逐个比较后续字符;

    若不等,从主串S的下一字符起,重新与T第一个字符比较。

         直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。

  否则,匹配失败,返回值 -1

 

2 Brute-Force算法的实现  

        typedef struct

       {  char str[MaxSize];

           int length;

        }String;

int BFIndex(String S, int start, String T)

   {       int i = start, j = 0, v;   

       while(i < S.length && j < T.length)

       {      if(S.str[i] == T.str[j])   {i++;      j++; }

              else{       i = i-j+1;  j = 0;          }

       }

            if (j==T.length) v=i-T.length;

           else v=-1;

       return v;

    }

3BF算法的时间复杂度

    讨论:

    若n为主串长度,m为子串长度,则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*mO(n*m)

    最好的情况是:一配就中!  只比较了m次。

    最恶劣情况是:主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位比较了m次,别忘了最后m位也各比较了一次,还要加上m!所以总次数为:(n-m)*m+m (n-m+1)*m

 

 能否利用已部分匹配过的信息而加快模式串的滑动速度?

   能!而且主串S的指针i不必回溯!最坏情况也能达到O(n+m)

 

请看KMP算法!

三、KMP算法
   1、KMP算法设计思想:

   尽量利用已经部分匹配的结果信息,尽量让i不要回溯,加快模式串的滑动速度。

 如图:


串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
 

 

需要讨论两个问题:

①如何由当前部分匹配结果确定模式向右滑动的新比较起点k

模式应该向右滑多远才是高效率的?

 如图:
串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
 
新起点 k怎么求?

 

根据模式串T的规律:   “T0…Tk-1”=“Tj-k …Tj-1”

由当前失配位置j(已知) ,可以归纳计算新起点 k的表达式。

 如图:


串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  

   (1k值仅取决于模式串本身而与相匹配的主串无关。

   (2k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。

   (3)这里的两部分子串可以有部分重叠的字符,但不可以全部重叠。

         next[j]函数表征着模式T中最大相同前缀子串和后缀子串(真子串)的长度。

    可见,模式中相似部分越多,则next[j]函数越大,它既表示模式T字符之间的相关度越高,也表示j位置以前与主串部分匹配的字符数越多。

    即:next[j]越大,模式串向右滑动得越远,与主串进行比较的次数越少,时间复杂度就越低(时间效率)。

 

    再想一想:如果主串是外存中一个大文件,用KMP算法效果又如何?

         如图:


串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
 

   下一个要讨论的问题是:如何用递推方式来求出最大相同子串的长度呢?这个问题一旦解决,整个KMP算法就可以掌握得很透彻了。

   求子串next[i]值的算法:

  void GetNext(String T, int next[])

  {        int j = 0, k = 0;

           next[0] = -1;

           while(j < T.length){

              if(T.str[j]==T.str[k])

              {   next[j+1]=k+1;  j++;  k++;      }

              else if (k==0){ next[j+1]=0;  j++;  }

         else k=next[k];

            }

   }

KMP算法的思想

s为主串,t为模式串,设i为主串s当前比较字符的下标,j为模式串t当前比较字符的下标,令ij的初值为0。当si = tj时,ij分别增1再继续比较;否则 i不变,j改变为next[j]值(即模式串右滑)后再继续比较。依次类推,直到出现下列两种情况之一:一是 j退回到某个j=next[j]值时有si = tj ,则 ij分别增1后再继续比较;二是j退回到j=-1时,令主串和子串的下标各增1,随后比较si+1t0 。这样的循环过程一直进行到变量大于等于S.length或变量j大于等于T.length时为止。

 

KMP算法的实现

  第一步,先把模式T所有可能的失配点j 所对应的next[j]计算出来;

  第二步:执行定位函数Index_kmp (与BF算法模块非常相似)

int KMPIndex(String S, int start,String T, int next[ ])

{int i=start,j=0,v;

    while ( i<=S.length && j<T.length ) {

      if (j==-1|| S.str[i] = = T.str[j] ) {i++;   j++ }   //不失配则继续比较后续字符

       else j=next[j];  //特点:S第一步,先把模式T所有可能的失配点j 所对应的next[j]

     }

  if(j==T.length) v=I-T.length; 

  else    v=-1;                  

return v;

}

主函数

void main(void)

  {       String S = {{"cddcdc"}, 6}, T = {{"cdc"}, 3};

           int next[8], pos;

           GetNext(T, next);

           pos = KMPIndex(S, 0, T, next);

           printf("pos = %d\n", pos);

   }

2KMP算法的时间复杂度

    回顾BF的最恶劣情况:ST之间存在大量的部分匹配,比较总次数为: (n-m+1)*mO(n*m)

    而此时KMP的情况是:由于指针i无须回溯,比较次数仅为n,即使加上计算next[j]时所用的比较次数m,比较总次数也仅为n+m=O(nm),大大快于BF算法

   注意:由于BF算法在一般情况下的时间复杂度也近似于O(n+m),所以至今仍被广泛采用。

KMP算法的用途:

   因为主串指针i不必回溯,所以从外存输入文件时可以做到边读入边查找——“流水作业

如图:


串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
 

  • 串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  • 大小: 26.5 KB
  • 串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  • 大小: 77.9 KB
  • 串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  • 大小: 24.1 KB
  • 串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  • 大小: 78.4 KB
  • 串的模式匹配算法理论与思想
            
    
    博客分类: C++   KMP   数据结构 算法  理论 C++   KMP   数据结构 算法  理论 
  • 大小: 34.6 KB