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

简介: KMP算法详解(理论+C语言代码实现)(下)

三:next数组特点的证明

四:next数组的优化:nextval数组

五.next数组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
}
//验证成功

以上就是KMP算法的详解,希望能对大家有所帮助!

目录
打赏
0
0
0
0
4
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
Paper2Code是由韩国科学技术院与DeepAuto.ai联合开发的多智能体框架,通过规划、分析和代码生成三阶段流程,将机器学习论文自动转化为可执行代码仓库,显著提升科研复现效率。
378 19
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
局域网行为监控软件 C# 多线程数据包捕获算法:基于 KMP 模式匹配的内容分析优化方案探索
本文探讨了一种结合KMP算法的多线程数据包捕获与分析方案,用于局域网行为监控。通过C#实现,该系统可高效检测敏感内容、管理URL访问、分析协议及审计日志。实验表明,相较于传统算法,KMP在处理大规模网络流量时效率显著提升。未来可在算法优化、多模式匹配及机器学习等领域进一步研究。
47 0
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
191 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
2157 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
c语言部分库函数,代码实现,以及细节理解
 代码来自:   http://blog.csdn.net/v_JULY_v     //得9 分 //为了实现链式操作,将目的地址返回,加2 分! char * strcpy( char *strDest, const char *strSrc ) { assert( (...
2783 0
|
5天前
|
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用,可以有效管理字符串和内存操作,它们是C语言编程中不可或缺的工具。
144 15
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
319 23

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问