kmp算法next求解详解
创始人
2025-05-29 05:31:35
0次
文章目录
- 前言
- 一、基本概念
- 二、next数组里的两种情况
- 1.产生两种情况的原因及介绍
- 2.p[j + 1] == p[i]时
- 3.p[j + 1] ！= p[i]时
- 总结
前言
相信大家在学习kmp算法时，如果会求next了，那么对于kmp算法基本就懂了，可是求解next数组的理解和求解比较困难，那么我今天就来详细的来讲解kmp算法的next的求解，此文章是建立在你对于kmp算法有一定的了解之后，而对于next的求解比较头疼的基础之上的，如果懂可以去自行了解(我之后可能会出kmp算法得完整详解)
一、基本概念
1️⃣“非平凡前缀”：指除了最后一个字符以外，一个字符串的全部头部组合。
2️⃣“非平凡后缀”：指除了第一个字符以外，一个字符串的全部尾部组合。（后面会有例子，均简称为前/后缀）
3️⃣s[ ]是模式串，即母串。
4️⃣p[ ]是模板串，即需要匹配的字符串
二、next数组里的两种情况
1.产生两种情况的原因及介绍
我们先拿一个典型的代码来做演示
for (int i = 1, j = -1; i < m; i ++ )//i从1开始是因为next第一个永远为-1，j从-1开始是为了后面下标j所在位置的next就是j所在的位置{ne[0] = -1;while (j >= 0 && p[j + 1] != p[i])//j+1也是为了使j的所在位置的next就是j所在的位置{j = next[j]；}if (p[j + 1] == p[i]) {j ++ ;}next[i] = j;}
2.p[j + 1] == p[i]时
3.p[j + 1] ！= p[i]时
🅿️其实这一步也是一个字符串匹配，只不过是利用了现有的条件，我这里举一个例子，当然例子只是用来帮助理解的
🔹>🔹
🔹
🔹
总结
相关内容
热门资讯
linux入门---制作进度条
了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学...
8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
JAVA多线程知识整理
Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP...
[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍
低功耗通用异步接收器（LPUART） 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振...
城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段...
程序的循环结构和random库...
第三个参数就是步长 引入文件时记得指明字符格式，否则读入不了 ...
中国版ChatGPT在哪些方面...
目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu...
2023 年 1 月 25 日，Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis...
Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比...
文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法
1. 前缀和 假设有一个数组，我们想大量频繁的去访问L到R这个区间的和，...
windows安装JDK步骤
一、 下载JDK安装包 下载地址：https://www.oracle.com/jav...
分治法实现合并排序(归并排序)...
🎊【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨...
在linux上安装配置node...
目录前言1，关于nodejs2，配置环境变量3，总结 前言...
Linux学习之端口、网络协议...
端口：设备与外界通讯交流的出口 网络协议： 网络协议是指计算机通信网...
Linux内核进程管理并发同步...
并发同步并发 是指在某一时间段内能够处理多个任务的能力，而 并行 是指同一时间能够处理...
opencv学习-HOG LO...
目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义
导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu...
写在前面 前期积累： GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...