【leetcode刷题】KMP算法如何理解和计算前缀表
创始人
2024-06-02 05:37:07
0

什么是最长相等前后缀?

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
在这里插入图片描述

其中黄色部分是前缀
绿色部分是后缀
这个字符串的最长相等前后缀是3

前缀表

前缀表(next数组):记录下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。
在这里插入图片描述

!!如何求前缀表

对第一个字符 其最长相等前后缀一定是0

next[0] = 0;

用for循环使指针i逐个后移,计算next[i]

for(int i = 1, j = 0; i
//计算过程}

指针i指向的是后缀的末尾
指针j指向的是与该后缀相同的前缀的末尾即next[i],或者第一个字符(没有相同的前后缀,next[i] = 0)

  • 上一轮找到相等的先后缀后,i和j都后移,当后移之后,前后缀末尾仍然相同时,说明此时最长相等前后缀 = 前一轮最长相等前后缀+1`
    在这里插入图片描述

  • 当后移后前后缀末尾不同时,即:
    在这里插入图片描述
    说明此时 最长相等前后缀长度小于j,需要将j前移,直至找到一个更小的最长相等前后缀next[i]
    由于是在上一轮找到相等前后缀的基础上后移得到的ij,因此前j-1个字符和i前面j-1个字符应该是一样的(灰色区域)
    由于i前面的前缀表是已知的,即知道next[j-1] = m

    那么next[j-1] = m意味着什么呢?
    意味着在前j-1个字符中,前m个和后m个字符形成的前后缀是一样的(浅蓝色区域)
    又 因为 前j-1个字符和i前面j-1个字符是一样的,因此最前面m个字符和i前面m个字符形成的前后缀是一样的,将j移动到next[j-1]
    比较s[j]是否等于s[i],若相等则找到了最长相等前后缀
    若仍然不等,则继续前移,直到前移到开头元素,说明没有相等的前后缀

在这里插入图片描述
完整代码为:

    void getNext(int* next, const string& s) {next[0] = 0;for(int i = 1, j = 0; iwhile (s[i] != s[j] && j > 0) {j = next[j - 1];}if(s[i] == s[j]) {next[i] = j + 1;j++;}else if( j == 0) {next[i] = 0;}}}

相关内容

热门资讯

122.(leaflet篇)l... 听老人家说:多看美女会长寿 地图之家总目录(订阅之前建议先查看该博客) 文章末尾处提供保证可运行...
育碧GDC2018程序化大世界... 1.传统手动绘制森林的问题 采用手动绘制的方法的话,每次迭代地形都要手动再绘制森林。这...
育碧GDC2018程序化大世界... 1.传统手动绘制森林的问题 采用手动绘制的方法的话,每次迭代地形都要手动再绘制森林。这...
Vue使用pdf-lib为文件... 之前也写过两篇预览pdf的,但是没有加水印,这是链接:Vu...
PyQt5数据库开发1 4.1... 文章目录 前言 步骤/方法 1 使用windows身份登录 2 启用混合登录模式 3 允许远程连接服...
Android studio ... 解决 Android studio 出现“The emulator process for AVD ...
Linux基础命令大全(上) ♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维...
再谈解决“因为文件包含病毒或潜... 前面出了一篇博文专门来解决“因为文件包含病毒或潜在的垃圾软件”的问题,其中第二种方法有...
南京邮电大学通达学院2023c... 题目展示 一.问题描述 实验题目1 定义一个学生类,其中包括如下内容: (1)私有数据成员 ①年龄 ...
PageObject 六大原则 PageObject六大原则: 1.封装服务的方法 2.不要暴露页面的细节 3.通过r...
【Linux网络编程】01:S... Socket多进程 OVERVIEWSocket多进程1.Server2.Client3.bug&...
数据结构刷题(二十五):122... 1.122. 买卖股票的最佳时机 II思路:贪心。把利润分解为每天为单位的维度,然后收...
浏览器事件循环 事件循环 浏览器的进程模型 何为进程? 程序运行需要有它自己专属的内存空间࿰...
8个免费图片/照片压缩工具帮您... 继续查看一些最好的图像压缩工具,以提升用户体验和存储空间以及网站使用支持。 无数图像压...
计算机二级Python备考(2... 目录  一、选择题 1.在Python语言中: 2.知识点 二、基本操作题 1. j...
端电压 相电压 线电压 记得刚接触矢量控制的时候,拿到板子,就赶紧去测各种波形,结...
如何使用Python检测和识别... 车牌检测与识别技术用途广泛,可以用于道路系统、无票停车场、车辆门禁等。这项技术结合了计...
带环链表详解 目录 一、什么是环形链表 二、判断是否为环形链表 2.1 具体题目 2.2 具体思路 2.3 思路的...
【C语言进阶:刨根究底字符串函... 本节重点内容: 深入理解strcpy函数的使用学会strcpy函数的模拟实现⚡strc...
Django web开发(一)... 文章目录前端开发1.快速开发网站2.标签2.1 编码2.2 title2.3 标题2.4 div和s...