使用next数组加速匹配过程-北京尧图网络

如果我们在匹配之前得到这么一个关于模式 p 的每一个位置 index 失去匹配后模式串的匹配指针应该调整为 next[index] 的 next 数组的话那么我们的匹配过程可以变成这样代码public class StrContainsKmp { public static boolean contains(String s, String p) { int ls s.length(), lp p.length(), i 0, j 0; int[] next getNext(p);//获取关于模式串p的next数组 while(i ls - lp j lp) { if(s.charAt(i) p.charAt(j)) { i; j; /* 如果模式串p的第一个字符p[0]和字符串s的当前字符s[i]都不匹配那么说明s中从i开始不可能匹配出p来因此换下一个开头继续尝试 */ }else if(j 0) i; /* 否则j位置不是0说明它前面有匹配成功的部分那么此时j应该调整为next[j]的位置 */ else j next[j]; } return j lp; } }next 数组能加速匹配过程可以从下面两个方面来理解保证 i 指针不回退指导 j 指针的调整在我们匹配失败的时候它可以利用我们之前已经匹配的部分字符串以前做过的努力在保证 i字符串 s 的匹配指针不回退的情况下指导此时指针 j模式串的匹配指针应该做怎样的调整。前面的图示已经向大家说明了这一点。跳过了一些无需验证的可能性还记得我们的暴力做法吗它尝试字符串 s 中每一个可能的开头位置即验证所有的可能性而 next 数组指导 j 的调整可以跳过一些根本不可能匹配出来模式串 p 的位置如下图所示这两种理解是等价的。

使用next数组加速匹配过程

相关推荐

Osg 开发三：OpenSceneGraph 变换节点及工程实例

Element Plus性能优化实战指南：三步实现高效组件库访问与开发体验

GoPro Python自动化控制终极指南：5个高级技巧释放相机全部潜力

更多资讯

【郑州工程技术学院主办 | 河南郑州召开 | SPIE出版】第三届模式识别与图像分析国际学术会议（PRIA 2026）

C++高性能爬虫框架设计与优化实践

Solon AI v3.10：Java全栈智能体开发框架解析

MiniPdf方：.NET开源Office转PDF的高效解决方案

基于高阶循环谱的MPSK载波频率估计与MATLAB实现

统一数据访问平台DataHub架构设计与实践

今日更新

基于高阶循环谱的MPSK载波频率估计与MATLAB实现

MiniPdf方：.NET开源Office转PDF的高效解决方案

Solon AI v3.10：Java全栈智能体开发框架解析

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？