学步园

 1、字符串匹配介绍       

        字符串匹配(String Matchiing)也称字符串搜索(String Searching)是字符串算法中重要的一种，是指从一个大字符串或文本中找到模式串出现的位置。

         如：文本串：P串 ASDFNMHUIOCIOHUIPNED

                模式串：  S串  HUIP

       S串在P串中对应位置如下所示

                P串 ASDFNMHUIOCIOHUIPNED

                S串                                         HUIP

2、字符串匹配算法

 （1）、回朔搜索法

算法思想：

    这是 一个最朴素的思路，将要模式串与文本字符串进行比较，有两种情况

      情况 1、若不匹配则模式串与下一个文本串进行比较

       如：P串 ASDFNMHUIOCIOHUIPNED

                S串  HUIP

        H和A不匹配则跳到下一个，将H与S进行比较，

    
如：P串     ASDFNMHUIOCIOHUIPNED

                S串       HUIP

        情况 2、若两个字符匹配，则将文本和模式串的指针都移动到下一个字符进行比较

            如P串 ASDFNMHUIOCIOHUIPNED

                    S串                   HUIP

                  P串的H与S串的H相匹配，所以将下一位P串中的U和S串中的U进行比较

          此时仍然会出现两种情况

    情况2.1、S串后面的字符与H串的一直相等，直到S串的末尾字符，则说明搜索成功，停止比较

           如：P串     ASDFNMHUIOCIOHUIPNED

                       S串                                            HUIP

          这是搜索成功的情况

  情况2.2、S串后面的某个字符与P串的不相等，说明此次匹配失败，将整个S串后移一位进行比较，同时S串指针移动到第一个字母，P串指针也移动到与S串对比的字符的位置，

          如：P串     ASDFNMHUIOCIOHUIPNED

                S串                             HUIP

          如上图，前面字符串HUI都是匹配的，到了第四个，P中的O与S中的P不再匹配了，说明此次匹配失败，S串后移

        如：P串     ASDFNMHUIOCIOHUIPNED

                S串                                HUIP

        P的指针从O移动到U，S中的指针从P移动到H；

    一直重复情况1、情况2步骤直到结束

算法评价：

     此算法虽然生动易懂，但算法复杂度太高。最坏的情况就是情况2.2中的最坏情况，每次都检索到最后一个才不匹配，此时算法复杂度为O（H.length*S.length）

     （2）KMP算法

    算法思想：

          KMP算法是对回朔搜索法中情况2.2的改进，相比蛮力算法，KMP 算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被叫做“部分匹配值表(Particial match table)”，它的设计是算法精妙之处。详情请看http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html，        

                在此说一下如何得到模式串部分匹配值next[i];

         如：S串：ABCDRTYABDABC

        1） 首先第0个字符（字符串从第0个算起）因为前面没有字符，不可能会有匹配情况，所以它的next值为0，

   即next[0]=0；

         2）定义俩个指针i，j分别指向S串字符即它的next值，因为第0个字符的next值已经知道，所以i初值为1，初始时i没有与任何字符进行匹配，故j初值为0；

        3）将S[i]与S[j]进行比较

       情况1：S[i]==S[j],说明第i个字符与前面的第j个字符匹配，匹配值加1；

     如：S串：ABCDRTYABDABC

        当匹配到红色A时，i=7，j=0，因为S[i]==S[j],所以到第i个字符的匹配值由0变成1；即j++，next[i]=j；即next[7]=1;     

      情况2：S[i]！=S[j],j==0；说明从0到第i个字符一直没出现匹配值，j不做处理

      情况3：S[i]！=S[j],j>0；说明前面一部分字符是匹配的，但是此时不匹配，此时另next[i]=j显然不合适，但另

next[i]=0也是不可以的，因为到i的后缀可能会与j的一个前缀相等，故要将j进行相应更改，另j=next[j-1];循环情况3

       如  S串： ABDABCCDABDABHV

        此时j=5，指向C；i=13，指向H，所以j=next[4]=1，指向第一个B；重复执行情况3，因为此时仍然满足情况3的条件，所以j=next[0]=0，再次执行情况3，不满足条件，跳到情况2；

重复执行情况1到情况3直到结束

代码实现如图所示：