模式匹配算法

《数据结构（C语言版）》上给出了两种模式匹配算法，BF算法和KMP算法。

存在一个主串S和一个模式T，要在主串S中查找与模式T相匹配的子串。

BF算法

操作步骤：

1. 分别利用计数指针i和 j 指示主串和模式T中当前正待比较的字符位置， i初值为 pos ，j 初值为 1；

2. 如果两个串均未比较到串 尾，即i 和j 均分别小于等于S和T的长度时，则循环执行以下操作：
   · S.ch[i] 和 T.ch[j]比较，若相等，则i和j分别指向串中的下个位置，继续比较后续字符；
   · 若不等，指针后退重新开始匹配，从主串的下一个字符( i = i - j+2）起再重新和模式的第一个字符（ j = 1）比较；

3. 如果j >T.length,说明匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号( i - T.length）；否则不成功，返回 0。

int index_BF(SqString s,SqString t，int pos)
{ 
      i = pos;j=1;
      while (i<s.length && j<t.length) 
      {
            if (s.ch[i]==t.ch[j]) 
            { 
                  i++; //依次匹配下一个字符 
                  j++; 
            } 
            else //回溯重新开始下一次匹配 
            { 
                  i=i-j+2; //主串从下一个位置开始匹配 
                  j=1; //子串从头开始匹配
            }
      } 
     if (j>=t.length) 
          return(i-t.length); //匹配成功
     else return 0; //模式匹配不成功
}

重要的在于理解BF如何变为更高大上的KMP

BF算法在运行时：如果模式与主串已经部分匹配，但最后一个出现了不匹配，那么按照BF算法，i回退到 i-j+2，j 回退到 1， 这样的话仅仅因为最后一个字符的不匹配便要抛弃一切再次开始(⊙﹏⊙)。

.

不过如果在多次的匹配过程中，有一次匹配出现了部分匹配，那么按照BF算法就要回退，继续，然后不匹配，不匹配···，直到有一次又出现了部分匹配，这个不断比较，后退，比较、后退的过程实在太那个什么了。

但仔细一想，之前有一次部分匹配了（也就是说在主串中有一段子串和模式的前面部分完全相同），然后按BF算法来说，要回退再重新开始比较，但这样继续下去（不断比较），其实不就是主串中一个与模式相同的子串进行比较吗（严谨来说回退后少了几个，不过如果部分匹配的部分较长的话，也是存在很多相同的）？ 那不就是等同于自己与自己比较了吗。

假设主串中那个与模式部分匹配的子串为s1，那么T中的为t1，在s1的部分与t1进行比较时，如果又出现了部分匹配(s1 的子串 s1'和 t1 的子串t1'），那么要是能早知道在s1的后面有与t1前面相同的小子串，那就不用回退那么多了，就直接回退到s1后面与t1'相同的部分不就省了很多步骤吗（也省了很多时间）。

KMP

既然如此，不如先把自己比较一遍，把结果存下来(next[]数组），下次又出现部分匹配的情况，就根据自己存下来的数据（本身的特点）合理的回退，这样就减少了冗余（本质或者说精髓是对模式进行预处理）。

KMP算法

next[]求解的自然语言定义：

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

2. 模式中第 j 个字符之前，前后（首尾）相等的最长真子串长度加一;

3. 其他next[j] = 1;

计算 next 函数值

void get_next(SString T,int next[])
{
     i=1;next[1]=0;j=0;
     while(i <T.length)
     {
          if(j==0||T.ch[i] == T.ch[j] ) { ++i; ++j; next[i] = j; }
          else  j = next[j];
     }
}

例：‘
模式串 a b a b c d a b c a
next [ ] 0 1 1 2 3 1 1 2 3 1
nextval 0 1 0 1 3 1 0 1 3 0

next[ ]值：

1. 第一个 a next[j] = 0 ,下一个；
2. b 之前只有一个 a ，next[j] = 1，下一个；
3. a 之前没有相等的字符， next[j] = 1；
4. b 之前的 a 与模式的首部 a 相同，相同字符数为 1 ，那么next[j] 为首尾相等的最长真子串长度加一 ，为 2；
5. c 之前的 ab 与首部的 ab 相同，同理 ，next[j] = 2+1 = 3;
6. d 之前没有首尾相等的真子串，为 1；
   ...

nextval[ ]值 :
算法：
· 第一位为 0；
· 从第二位开始，模式的字符要和其 next[] 的值（这个值要比自己的位置号小）所对应的字符相比，如果相等，第 i 位的 nextval[ i ] = nextval[ next[ i ] ]，如果不等，把其next值照抄下来即可；

1. nextval[ 1 ] =0；

2. 在第二位开始， nextval [ i ] 等于将该位的字符与该位的next[] 的值所指向的字符比较，即 第二位为 b ，其next[] 数据为 1 ,则将 b 与 模式的第 1 个 ( a ) 比较 ， b 不等于 a ，那么nextval[] 等于 next[] 值，如果相等则 nextval [ i ] = naxtval[ naxt[ i ] ] ；

3. a ，next[ i ]值为 1 ，和模式第一个比较，相同，nextval[ i ] = nextval[ next[ i ] ] = 0；

4. b， next[ i ]值为 2 ，和第二个比较，相等 ，nextval[i] = nextval[ next[i] ] = nextval[ 2 ] = 1；
   ...

验证 ：

串 " ababaabab " 的 nextval 为 010104101.