42｜串的KMP模式匹配算法之实现与性能分析：代码实现简单

王健伟

你好，我是王健伟。
上节课我们针对串的 KMP 模式匹配算法配以了大量的图形进行了非常仔细的观察，而观察的目的，就是为了这节课代码的实现。
串的 KMP 模式匹配算法实现代码并不多，但只有你学好了上节课的内容，对该算法有详细的理解，才能理解本节这样写代码的含义。
KMP 模式匹配算法实现代码KMP 模式匹配算法实现代码各式各样，有些实现方法虽然简洁，但并不好理解，我这里先以比较容易理解的方式进行代码实现。你可以先仔细读一遍。
//求本串的next数组
void getNextArray( int next[])
{
  //next数组下标为0和为1的元素值固定为0和1。其实next[0]里的值并没有用到
  if (length < 1)
    return;
  
  //next数组的前两个元素肯定是0和1
  if (length == 1) //只有一个字符
  {
    next[0] = 0;
    return;
  }
    
  next[0] = 0;
  next[1] = 1;
  if (length == 2) //只有二个字符
  {
    return;
  }
    
  //至少三个字符
  int nextarry_idx = 2; //当前要处理的next数组下标
  int max_pub_zhui = 0; //max_pub_zhui：最大公共前后缀包含的字符数量
  
  //循环的目的是给next数组赋值
  while (nextarry_idx < length) 
  {
    int left_RMC_count = nextarry_idx; //left_RMC_count：如果当前字符与主串的字符不匹配，当前字符左侧有多少个字符
    int max_pub_zhui = left_RMC_count - 1; //max_pub_zhui：最大公共前后缀包含的字符数量
    
    int start1idx = 0;
    int start2idx = left_RMC_count - max_pub_zhui;
    
    int xhtimes = max_pub_zhui; //循环次数
    
    //本循环的目的是获取最长公共前后缀长度，代码写法无固定方式，选择自己容易理解的方式写即可
    while (xhtimes > 0)
    {
      if (ch[start1idx] != ch[start2idx])
      {
        max_pub_zhui--;
        start1idx = 0;
        start2idx = left_RMC_count - max_pub_zhui;
        xhtimes = max_pub_zhui;
        continue; //要回去重新循环
      }
      else
      {
        start1idx++;
        start2idx++;
      }
      xhtimes--;
    } //end while (xhtimes > 0)
    next[nextarry_idx] = max_pub_zhui + 1; //如果公共前后缀长度为n，那么就需要用子串的第n+1个字符与主串当前位做比较。
    nextarry_idx++;
  } //end while
  return;
}
  
//KMP模式匹配算法接口，返回子串中第一个字符在主串中的下标，如果没找到子串，则返回-1
//next：下一步数组（前缀表/前缀数组）
//pos：从主串的什么位置开始匹配子串，默认从位置0开始匹配子串
int StrKMPIndex(const MySString& substr, int next[], int pos = 0)
{
  if (length < substr.length) //主串还没子串长，那不可能找到
    return -1;    
  
  int point1 = pos; //指向主串
  int point2 = 0;  //指向子串
  
  while (ch[point1] != '\0' && substr.ch[point2] != '\0')
  {
    if (ch[point1] == substr.ch[point2])
    {
      //两个指针都向后走
      point1++;
      point2++;
    }
    else //两者不同
    {
      //point1和point2两个指针的处理
      
      if (point2 == 0) //下标0号位置子串的字符如果与主串字符不匹配则后续就要用子串的第1个字符（字符a）与主串下一位（1号下标位）字符做比较 
      {
        point1++; //主串指针指向下一位
      }
      else
      {
        //走到这个分支的，主串指针point1不用动，只动子串指针point2
        point2 = next[point2] - 1; //第这些个子串中的字符与主串当前位字符做比较
      }
    }
  }//end while
  
  if (substr.ch[point2] == '\0')
  {
    //找到了子串
    return point1 - point2;
  }
  return -1;
}

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文详细介绍了KMP模式匹配算法的实现和性能分析。作者王健伟强调了对算法内容的详细理解对于正确理解代码含义的重要性。文章包括KMP模式匹配算法的实现代码和性能分析，为读者提供了学习和理解该算法的重要指导。具体内容包括KMP模式匹配算法的实现代码，包括求解next数组和KMP模式匹配算法接口的实现。此外，还介绍了求解next数组的高效新版本代码，并通过图示和分析阐述了如何根据已知的next元素值推导出下一个未知的值。文章内容深入浅出，既有具体的代码实现，又有理论知识的阐述，适合读者快速了解KMP模式匹配算法的核心概念和实现细节。KMP算法的时间复杂度是O(m+n)，空间复杂度为O(m)。文章还提供了思考题，引导读者深入思考和互动讨论。整体而言，本文为读者提供了全面而深入的KMP模式匹配算法的学习资料。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68

立即购买

登录后留言

精选留言

由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。

收起评论