//next数组保存是，失配后，返回前面字符串的最大相似度的地方 
static int *Get_next(const char *sub) 
{ 
      int len = strlen(sub); 
      int *next = (int *)malloc(sizeof(int) * len); 

      next[0] = -1; 
      next[1] = 0; 

      int j = 1; 
      int k = 0; 
      while(j+1 < len)//j+1是通过已知求未知的未知位置，求的这个未知位置得合法，在数组长 度内就合法 
      { 
           if((k==-1) ||sub[j] == sub[k]) 
           { 
                 next[++j] = ++k; 
                 /*k++;
                    j++; 
                    next[j] = k;*/ 
           }
          else 
           { 
                 k = next[k];
            } 
        }
        return next; 
}

//KMP算法，特点：i打死不回退，时间复杂度O（n+m） 
int KMP_Search(const char* str, const char *sub, int pos) 
{ 
        //断言 防止指针为NULL 并且防止pos位置非法 
        if(str == NULL || sub == NULL || pos < 0 || pos >= strlen(str)) return -1; 

        int lenstr = strlen(str);//获取主串长度 
        int lensub = strlen(sub);//获取子串长度 

        int i = pos;//i代表主串的判断位置 得从pos开始判断 
        int j = 0;// j代表子串的判断位置 

        int *next = Get_next(sub); 
        while(i<lenstr && j<lensub)//如果主串和子串都没走到头，就继续进行 
        { 
              if((j == -1) || str[i] == sub[j])//两者相等，则同时向后走 
              { 
                    i++; 
                    j++; 
               }
              else//不相等，根据回退规则，进行回退即可 
              { 
                    //i = i-j+1;//i打死不回退 
                    //j = 0; j回到到next[j]里面 
                    j = next[j]; 
               } 
          }

          free(next); 
          //while退出，有两种情况，1.没找到 2.找到了 
          if(j >= lensub)//如果子串走到头，则判断找到了 
          { 
                return i-j; 
          }
          return -1; 
      }


//朴素（BF）查找算法 特点：1.相等，同时向后走 2.如果不相等，j回退到0，而i回退的i-j+1 
// 3.如果j走除了范围，证明找到了，返回值为i-j 
//面试笔试必考，不会也得背过 
int BF_Search(const char* str, const char *sub, int pos) 
{ 
       //断言 防止指针为NULL 并且防止pos位置非法 
       if(str == NULL || sub == NULL || pos < 0 || pos >= strlen(str)) return -1; 

       int lenstr = strlen(str);//获取主串长度 
       int lensub = strlen(sub);//获取子串长度 

       int i = pos;//i代表主串的判断位置 得从pos开始判断 
       int j = 0;// j代表子串的判断位置 

       while(i<lenstr && j<lensub)//如果主串和子串都没走到头，就继续进行 
       { 
              if(str[i] == sub[j])//两者相等，则同时向后走 
              { 
                     i++;
                     j++; 
              }
              else//不相等，根据回退规则，进行回退即可 
              { 
                     i = i-j+1; 
                     j = 0; 
               } 
        }
        //while退出，有两种情况，1.没找到 2.找到了 
        if(j >= lensub)//如果子串走到头，则判断找到了 
        { 
               return i-j; 
         }
         return -1; 
}

int main() 
{ 
         const char *a = "ababcabcdabcde"; 
         const char *b = "abcd"; 
         int tmp = KMP_Search(a, b, 6); 
         printf("%d\n", tmp); 
         return 0; 
}