串的模式匹配算法---KMP算法和朴素模式匹配算法（C语言版）

1.朴素模式匹配算法：
(1)王道代码

int Index (SString S,SString T){
       int k=1;//设置k，为主串后退标记
       int i=k, j=1;
       while(i<=S.length&&i<=T.length){
              if( S.ch[i]=T.ch[j] ) {
                   i++;
                   j++;//继续比较后续的字符
              }
              else{
                  k++;//检查下一个子串
                  i=k;
                  j=1;
              }
      if( j>T.length)     return k;

      else  return 0;
}

(2)课本代码

int Index (SString S,SString T){
       int i=i, j=1;
       while(i<=S.length&&i<=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;
}

这两个代码的时间复杂度都为O(nm);

2.KMP算法
(1)主体算法：

int Index_KMP(SString S, SString T, int next[] ) {
          int i=1, j=1;
          while(i<=S.length && i<=T.length) {
                  if( S.ch[i] == T.ch[j] ) {
                         i++；
                         j++；//继续比较后续字符
                   }
                   else{
                         j=next[j]; //模式串向右移动
                   }
          }
          if(j > T.length)
                  return i-T.length;  //匹配成功
          else
                  return 0;
}

(2)关于next[ ] 数组的形成：
串的前缀：包含第一个字符，但不包含最后一个字符的子串
串的后缀：包含最后一个字符，但不包含第一个字符的子串
当第 j 个字符匹配失败，由前1~j-1 个字符组成的串记为 S，则：
next[ j ] = S的最长相等的前后缀长度加1；
特别地：next[ 1 ]=0; next [2] = 1;

初级代码：

void get_next( SString T , int next [  ]) {
          int i=1, j=0; // i控制后缀长度，j控制前缀长度
          next[1]=0;
          while(i 
改进代码：
 
void get_next( SString T , int next [  ]) {
          int i=1, j=0; // i控制后缀长度，j控制前缀长度
          next[1]=0;
          while(i