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

相关内容

热门资讯

cmseasy oday-CM... 大家好，今天我要给大家爆个猛料！你们听说过CMSEasy吗？就是那个看起来挺靠谱的建站系统，最近居然...
番茄花园u盘装系统-番茄花园 ... 嘿，大家好！今天我要来聊聊那个让我爽到飞起的经历——用番茄花园U盘装系统！没错，就是那个传说中的神器...
windows81正式版密钥-... 哎呀，说到这个Windows8.1正式版密钥，我可是有一肚子的话要说啊！记得那会儿，我刚装上了这个新...
win10驱动开发-Win10... 哎呀，说到Win10驱动开发，我可真是有话要说！这可不是什么轻松的活儿，简直就像是在数字世界里打怪升...
什么是心悸-心悸：身体与情绪的... 心悸，这个词听起来就像是一首未完的旋律，总是在不经意间悄悄响起。它不是那种平淡无奇的感觉，而是让你的...
帝国cms 列表内容模板-帝国... 哎呀，说到帝国CMS的列表内容模板，我这心里真是五味杂陈啊！你知道吗，每次我打开后台，看到那些密密麻...
蛋白肺：默默无闻的健康守护者，... 在这个世界上，有一种东西，它默默无闻，却支撑着我们的每一次呼吸，那就是蛋白肺。听起来可能有点陌生，但...
河南省户籍管理规定-河南户口：... 哎呀，说到河南的户口，我这心里头就像打翻了五味瓶，酸甜苦辣全都有啊！你知道吗，在咱河南，户口这事儿可...
cad丢失msvcp140dl... 哎呀，真是气死我了！今天本来想好好画个图，结果一打开CAD，就弹出来一个什么“丢失msvcp140d...
arcscene中的三维符号-... 大家好！今天我要带你们一起跳进ArcScene这个神奇的世界，去看看那些让人眼花缭乱的三维符号！想象...
window mac主题-Wi... 嘿，朋友们，今天咱们来聊聊那些天天陪着我们的电脑小伙伴——Windows和Mac。你知道吗，每次我打...
全国查重名网站数据惊人，你的名... 哎呀，说到这个全国查重名网站，我这心里就五味杂陈的！你知道吗，现在想要一个独一无二的名字，比中彩票还...
server2024企业版is... 哎呀，说到这个Server2024企业版ISO，我这心里头的小激动真是按捺不住！你知道吗，这不仅仅是...
windows 2024 sp... 哎呀，说到这Windows2024SP1补丁啊，真是让人又爱又恨！你知道的，每次系统更新，心里总是七...
公安系统网站：信息全、办事便捷... 哎呀，说到公安系统的网站，那可是咱们老百姓的贴心小棉袄啊！每次有什么事情，比如身份证丢了，或者想知道...
狗狗肛门失禁怎么办？快来看看这... 哎呀，说到这个话题，我这心里就五味杂陈的。我家那小可爱，最近不知道怎么了，总是时不时地就“漏”了。你...
探索电控系统电路图：现代科技的... 大家好，我是电控系统电路图的狂热爱好者，今天我要和大家聊聊这些常常藏在机器背后的神秘图纸。你们知道吗...
浅表性胃炎用什么药-浅表性胃炎... 哎呀，说到浅表性胃炎，真是让人头疼啊！每次胃一疼，整个人都不好了。你知道吗，这浅表性胃炎，其实就是胃...
易分销21-易分销 21：销售... 在商海沉浮的日子里，每一次的销售都是一场心跳加速的冒险。今天，我要跟大家聊聊这颗新星——易分销21，...
高血脂的护理计划-高血脂别头疼... 哎呀，说到高血脂，我这心里就五味杂陈的。你知道吗，这胆固醇就像是个调皮的小鬼，悄悄地在我身体里捣乱，...