【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]。
    由于是在上一轮找到相等前后缀的基础上后移得到的i和j，因此前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;}}}
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：@Builder注解使用

下一篇：【Maven】依赖管理—导入jar包的三种方式、依赖范围设置

相关内容

热门资讯

安卓系统怎么拼写啊,Andro... 你问这个问题可真是戳中了我的技术盲区呢！安卓系统，这个名字听起来是不是很熟悉，就像你的手机里那个无所...
华为安卓系统被停用,挑战与转型... 你知道吗？最近科技圈可是炸开了锅！华为安卓系统被停用，这可不是一个小新闻哦。咱们得好好聊聊这个话题，...
安卓王者荣耀观战系统,沉浸式观... 亲爱的手机游戏爱好者们，你是否曾在王者荣耀的战场上，因为错过队友的精彩操作而扼腕叹息？或者，你是否渴...
怎么加安卓12系统,安卓12系... 你有没有发现，安卓系统每次更新都像是在给我们的小手机来一次华丽变身呢？这不，安卓12已经悄悄地来了，...
安卓系统阿联酋航空积分,便捷积... 你有没有想过，你的安卓手机里那些累积的积分，竟然可以在阿联酋航空的旅途中派上大用场？没错，就是那个带...
安卓系统录音文件位置,录音文件... 你有没有遇到过这种情况：手机里突然冒出了很多录音文件，但你就是找不到它们藏在哪里？别急，今天就来给你...
安卓灵动岛系统自带,智能交互新... 你知道吗？最近安卓手机界可是掀起了一股不小的风潮，那就是——安卓灵动岛系统自带功能！是不是听起来就让...
安卓支持ios系统下载,下载体... 你知道吗？最近在科技圈里可是掀起了一股小小的热潮呢！那就是安卓手机竟然支持iOS系统下载应用了！是不...
火山安卓加验证系统,安全与便捷... 你知道吗？在科技飞速发展的今天，手机安全可是个大问题。尤其是安卓系统，作为全球使用最广泛的操作系统之...
简化系统app安卓版,高效便捷... 你有没有发现，现在的生活节奏越来越快，信息爆炸的时代，我们每天都要处理海量的数据和信息。在这个时候，...
surfacepro2安卓系统... 你有没有想过，一台笔记本电脑竟然能像智能手机一样灵活多变？没错，今天我要跟你聊聊的就是这款神奇的设备...
安卓手机车联网系统,智能驾驶的... 你有没有发现，现在开车出门，手机已经成了我们离不开的好伙伴？没错，说的就是那个神奇的安卓手机车联网系...
将安卓系统数据导入ios系统,... 你是不是也有过这样的经历：手机里存满了珍贵的照片、联系人、应用数据，突然有一天，你决定换一台iPho...
雷霆战机 安卓最低系统,系统要... 你有没有听说过这款超级酷炫的飞行游戏——雷霆战机？没错，就是那个让你一上手就停不下来的刺激游戏！今天...
电脑独立安装安卓系统,探索电脑... 电脑独立安装安卓系统：探索未来的可能性在当今这个数字化时代，电脑已经不仅仅是一个用来打字的工具，它更...
树莓派虚拟安卓系统,打造便携式... 你有没有想过，用树莓派来运行安卓系统？听起来是不是有点酷炫？想象一个迷你的小树莓派，竟然能变身成为一...
安卓系统如何安装tk,安卓系统... 你有没有想过，你的安卓手机里装个tk，生活是不是能变得更有趣呢？别急，别急，我来给你详细说说怎么操作...
安卓计步数系统,健康生活新伙伴 你有没有发现，每天手机里那个默默无闻的安卓计步数系统，竟然悄悄地记录了你走过的每一步？今天，就让我带...
安卓原生系统真的好吗,究竟是否... 你有没有想过，安卓原生系统到底是不是那个传说中的“好”？咱们今天就来聊聊这个话题，看看这个系统到底有...
安卓2.3系统开机画面,复古与... 亲爱的读者，你是否还记得那些充满怀旧情怀的安卓2.3系统开机画面？那个曾经陪伴我们度过无数时光的小图...