KMP算法详解(理论+C语言代码实现)（下）

/*
str:代表主串
sub:代表字串
pos:代表从主串的pos位置开始找
*/
void GetNext(char* sub, int* next,int lenSub)
{
  next[0] = -1;
  //子串长度为1,直接返回即可
  if (lenSub == 1)
  {
    return;
  }
  next[1] = 0;
  int i = 2;//当前i下标
  //因为此时还不知道next[i]的值,只知道next[i-1]的值和sub[k]的值
  int k = 0;//前一项的k
  while(i<lenSub)
  {
    //k==-1,此时不能再进行回退了,否则子串会发生越界
    //匹配成功或者k回退到k=-1时,利用next[i-1]=k,推出=>>next[i]=k+1;
    //i和k往后走,继续求解next数组
    if (k==-1 || sub[i - 1] == sub[k])
    {
      next[i] = k + 1;
      i++;
      k++;
    }
    //sub[i-1]!=sub[k],即匹配不成功,k回退
    else
    {
      k = next[k];//k回退
    }
  }
}
int KMP(const char* str,const char* sub, int pos)
{
  //对参数的正确性的判断
  assert(str!=NULL && sub!=NULL);
  int lenStr = strlen(str);
  int lenSub = strlen(sub);
  if (lenStr == 0 || lenSub == 0)
  {
    return -1;
  }
  if (pos < 0 || pos >= lenStr)
  {
    return -1;
  }
  int* next = (int*)malloc(sizeof(int) * lenSub);
  assert(next != NULL);
  GetNext(sub, next, lenSub);
  //开始遍历两个串
  int i = pos;//遍历主串
  int j = 0;//遍历子串
  while (i < lenStr && j < lenSub)
  {
    //对应位置相等,往后走
    //j==-1,此时不能再进行回退了,否则子串会发生越界
    if (j == -1 || str[i] == sub[j])
    {
      i++;
      j++;
    }
    //否则:i不动,j回退
    else
    {
      j = next[j];
    }
  }
  //子串遍历结束,意味着匹配成功
  free(next);
  next = NULL;
  if (j >= lenSub)
  {
    return i - j;
  }
  //主串遍历成功,子串却没有遍历成功,意味着匹配失败
  return -1;
}
//验证
int main()
{
  printf("%d\n", KMP("ababcabcdabcde", "abcd", 0));//5
  printf("%d\n", KMP("ababcabcdabcde", "abcdf", 0));//-1
  printf("%d\n", KMP("ababcabcdabcde", "e", 0));//13
  printf("%d\n", KMP("d", "e", 0));//-1
}
//验证成功