【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包的三种方式、依赖范围设置

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗？在安卓系统里，华为的应用可是个宝库呢！它们不仅功能强大，而且使用起来超级方便。今天，就让我...
安卓变ios系统魅蓝 你知道吗？最近有个朋友突然告诉我，他要把自己的安卓手机换成iOS系统，而且还是魅蓝品牌的！这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们，你是否曾在某个夜晚，被一本神奇的书所吸引，仿佛它拥有着穿越时空的力量？今天，我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去，这可真是让人头疼的问题啊！你是不是也遇到了这种情况，心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过，用键盘来控制你的安卓手机？是的，你没听错，就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过，你的小米手机里有一个隐藏的宝藏——安卓镜像系统？没错，就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过，每天忙碌的工作中，有没有什么好帮手能帮你轻松管理时间呢？今天，就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们，你是否曾梦想过将安卓系统搬到你的电脑桌面上？想象那些流畅的动画、丰富的应用，还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们，你是否对安卓13系统充满好奇？想要一探究竟，却又苦于没有足够的时间去研究？别担心，今天...
车机安卓7.1系统,功能升级与... 你有没有发现，现在的车机系统越来越智能了？尤其是那些搭载了安卓7.1系统的车机，简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况：手机里存了一大堆PDF文件，可是怎么也找不到一个能顺畅阅读的工具？别急，今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过，为什么你的手机里装的是安卓系统呢？安卓系统，这个名字听起来是不是有点神秘？今天，就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过，如果苹果手机突然变成了安卓系统，会是怎样的景象呢？想象那熟悉的苹果外观，却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦？没错，就是那个让手机焕然一新的安卓12.0系统！那么，咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗？在科技的世界里，有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们，你是否曾觉得安卓系统的屏幕颜色不够个性，或者是因为长时间盯着屏幕而感到眼睛疲劳？别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年，性能逐渐力不从心，却又不忍心让它退役呢？别急，今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统：一场技术革新还是政治博弈？在数字化时代，智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现，手机里的安卓系统日记本，简直就是记录生活点滴的宝藏库呢？想象每天忙碌的生活中，有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现，用安卓手机的时候，广告总是无处不在，让人烦得要命？不过别急，今天我要给你揭秘一个秘密—...