补充 kmp算法

kmp算法是基最长的前后缀和
我们把模式串和查找串放在一起，如果他们前后缀长度等于模式串，说明我们找到对应的位置
假设现在遍历到第i 个节点，前一个节点的前后缀长度是p[i-1]
如果s[i]==s[p[i-1]] 说明可以延续之前的最长p[i]=p[i-1]+1
如果不等于，我们可以以前一个节点结尾的第二个最长的前后缀长度，也就是 p[p[i-1]-1]
因为可以确定的是 s[0:p[i-1]-1]的长度是之前相等的前缀,我们想找的第二长的前后缀长度就是字符串s[0:p[i-1]-1]的最长前后缀长度
注意这里字符串的表示方法两边都能取到
不断循环找到最长的前后缀长度

我们找的前后缀长度不包括自身，也就是一个字母的最长前后缀长度是 0

这样我们初始比较可以和第一个进行比较（也就是索引 0 的节点此时p[i-1]=0）

全部评论

推荐最新楼层

11-13 12:55

元戎启行_软件工程师(准入职员工)

元戎启行内推，元戎启行内推码

元戎启行嵌入式面经(友好)(初次面)    开局直接讲项目，我把最拿得出手的项目一讲(tc377 gps+九轴陀螺仪+摄像头+图像处理)的比赛。期间被多处细问但完美解决。    然后问了一个spi通信原理，我给忘了(我怎么能把这给忘了啊😤😤)，只讲了个大概。    问了一个pid，p i d各自含义及用处。    跟面试官讲实话:我才开始背八股文，C++和数据结构还没咋预习，C语言最熟。也就只问了最简单的C语言。(面试官人真的很好😭😭😭)    问了一个二维数组地址是否连续。    问了一个在64位系统下。    short i[]={0，1}    printf(sizeof(i)...

点赞评论收藏

11-13 10:17

门头沟学院 Java

美团java日常实习

昨天面美团，jvm，juc问的好深啊，感觉小林coding不太够喔，牛油们有没有什么推荐的八股网站嘛🕒 岗位/面试时间👥 面试题目🤔 面试感受

明天不下雨了：小林Coding：https://xiaolincoding.com/ 全栈哥：https://www.pdai.tech/ Guide哥：https://javaguide.cn/ 秀哥：https://interviewguide.cn/ 沉默王二：https://javabetter.cn/home.html 磊哥：https://www.javacn.site/interview/basic/ 小傅哥：https://bugstack.cn/ 源码哥：https://doocs.github.io/source-code-hunter/#/ 各大厂的公众号技术文章和一些经典的书籍

面试太紧张了怎么办？

点赞评论收藏