【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系统跳转到安卓系统，会是怎样的体验呢？这可不是天方夜谭，随着科技...
安卓系统网络连接查看,安卓系统... 你有没有遇到过这种情况：手机里装了各种APP，可就是不知道哪个在偷偷消耗着你的流量？别急，今天就来教...
什么安卓系统优化的好,打造流畅... 你有没有发现，手机用久了，就像人一样，会变得有些“臃肿”呢？尤其是安卓系统，有时候感觉就像一个老态龙...
手机安卓系统ios系统怎么安装... 你有没有发现，现在手机里的软件真是五花八门，让人眼花缭乱？无论是安卓系统还是iOS系统，都能轻松安装...
按音量键报警安卓系统,安卓系统... 你有没有遇到过这种情况：手机突然发出刺耳的警报声，吓得你心跳加速，还以为发生了什么大事？别担心，今天...
安卓系统改win版系统怎么安装... 你有没有想过，把你的安卓手机换成Windows系统的电脑呢？想象那流畅的触控体验和强大的办公功能，是...
安卓系统如何备份到苹果,轻松实... 你是不是也有过这样的烦恼：手机里的照片、联系人、应用数据等等，突然间就消失得无影无踪？别担心，今天就...
修改安卓系统参数设置,安卓系统... 你有没有发现，你的安卓手机有时候就像一个不听话的小孩子，总是按照自己的节奏来，让你有点头疼？别急，今...
安卓手机gps定位系统,畅享智... 你有没有发现，现在不管走到哪里，手机都能帮你找到路？这都得归功于安卓手机的GPS定位系统。想象你站在...
华为不能安卓系统升级,探索创新... 你知道吗？最近有个大新闻在科技圈里炸开了锅，那就是华为的新款手机竟然不能升级安卓系统了！这可真是让人...
汽车加装安卓系统卡住,探究原因... 你有没有遇到过这样的尴尬情况：汽车加装了安卓系统，结果屏幕突然卡住了，就像被施了魔法一样，怎么也动弹...
电量壁纸安卓系统下载,打造个性... 手机电量告急，是不是又得赶紧找充电宝了？别急，今天就来给你安利一款超实用的电量壁纸，让你的安卓手机瞬...
iPhonex里面是安卓系统,... 你有没有想过，那个我们每天都离不开的iPhone，里面竟然可能是安卓系统？是的，你没听错，就是那个以...
ios系统比安卓系统好在哪里,... 你有没有想过，为什么有些人对iOS系统情有独钟，而有些人却对安卓系统爱不释手呢？今天，就让我带你从多...
安卓系统跟踪设置大小,跟踪设置... 你知道吗？现在智能手机几乎成了我们生活的必需品，而安卓系统作为全球最受欢迎的操作系统之一，它的跟踪设...
在线迎新系统下载安卓,轻松开启... 你有没有想过，开学季的到来，就像一场盛大的狂欢，而在这个狂欢中，有一个小助手，它默默地守护着你的入学...
安卓系统怎么申请微信号,一键申... 你有没有想过，在安卓手机上申请一个微信账号，竟然也能变得如此简单？没错，就是那个我们每天离不开的社交...
安卓手机系统里怎么清理,轻松优... 手机里的东西越来越多，是不是感觉安卓手机系统越来越慢了呢？别急，今天就来教你怎么清理安卓手机系统，让...