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

 串的模式匹配算法

一、基本概念

1、模式匹配（定位）

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

 

2、算法目的

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

 

3、算法种类

     BF算法  （又称古典的、经典的、朴素的、穷举的）

 

          KMP算法

1、Brute-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;

    }

3、BF算法的时间复杂度

    讨论：

    若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(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算法
   １、KMP算法设计思想：

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

 如图：

 

 

需要讨论两个问题：

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

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

 如图：

 新起点 k怎么求？

 

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

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

 如图：

  

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

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

   （3）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。

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

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

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

 

    再想一想：如果主串是外存中一个大文件，用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当前比较字符的下标，令i和j的初值为０。当si = tj时，i和j分别增1再继续比较；否则 i不变，j改变为next[j]值（即模式串右滑）后再继续比较。依次类推，直到出现下列两种情况之一：一是 j退回到某个j=next[j]值时有si = tj ，则 i和j分别增1后再继续比较；二是j退回到j=-1时，令主串和子串的下标各增1，随后比较si+1和t0 。这样的循环过程一直进行到变量大于等于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);

   }

2、KMP算法的时间复杂度

    回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)*m＝O(n*m)

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

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

KMP算法的用途：

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

如图：