代码随想录算法训练营第九天|KMP算法、字符串总结

KMP算法

帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili

基础知识

1、前缀：包含首字母，不包含尾字母的所有字串。如"aabc"的前缀为a, aa, aab;
2、后缀：包含尾字母，不包含首字母的所有字串。如"aabc"的后缀为c, bc, abc；
3、最长相等前后缀：aabc ,0；aabaa, 2；
4、前缀表：字符串每个前缀序列+自身的最长相等前后缀的表，如字符串"aabaaf" 的前缀表为010120，(a, 0; aa, 1; aab, 0; aaba, 1; aabaa, 2; aabaaf,0）

5、在匹配失败位置的前一位对应前缀表的值，就是跳到继续匹配位置的下标。

image.png

，一般用next表示（下次要回退的位置）

待填坑

字符串总结

代码随想录 (programmercarl.com)
python中字符串是不变量，一般都需要先转换成list再进行操作

• 人面猴

  序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...

  沈念sama阅读 214,377评论 6赞 496
• 死咒

  序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...

  沈念sama阅读 91,390评论 3赞 389
• 救了他两次的神仙让他今天三更去死

  文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...

  开封第一讲书人阅读 159,967评论 0赞 349
• 道士缉凶录：失踪的卖姜人

  文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...

  开封第一讲书人阅读 57,344评论 1赞 288
• 港岛之恋（遗憾婚礼）

  正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...

  茶点故事阅读 66,441评论 6赞 386
• 恶毒庶女顶嫁案：这布局不是一般人想出来的

  文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...

  开封第一讲书人阅读 50,492评论 1赞 292
• 城市分裂传说

  那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...

  沈念sama阅读 39,497评论 3赞 412
• 双鸳鸯连环套：你想象不到人心有多黑

  文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...

  开封第一讲书人阅读 38,274评论 0赞 269
• 万荣杀人案实录

  序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...

  沈念sama阅读 44,732评论 1赞 307
• 护林员之死

  正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...

  茶点故事阅读 37,008评论 2赞 328
• 白月光启示录

  正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...

  茶点故事阅读 39,184评论 1赞 342
• 活死人

  序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...

  沈念sama阅读 34,837评论 4赞 337
• 日本核电站爆炸内幕

  正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...

  茶点故事阅读 40,520评论 3赞 322
• 男人毒药：我在死后第九天来索命

  文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...

  开封第一讲书人阅读 31,156评论 0赞 21
• 一桩弑父案，背后竟有这般阴谋

  文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...

  开封第一讲书人阅读 32,407评论 1赞 268
• 情欲美人皮

  我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...

  沈念sama阅读 47,056评论 2赞 365
• 代替公主和亲

  正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...

  茶点故事阅读 44,074评论 2赞 352

推荐阅读更多精彩内容

• 代码随想录算法训练营第九天|28. 实现 strStr() 459.重复的子字符串 字符串总结...

  28.实现 strStr() （本题可以跳过） 因为KMP算法很难，大家别奢求一次就把kmp全理解了，大家刚学KM...

  window_shopper阅读 164评论 0赞 0
• 代码随想录算法训练营第九天| 字符串part02

  （真的很忙，所以博客记录得非常粗糙，见谅） 文章链接: 28.实现strStr()：https://program...

  泠君阅读 34评论 0赞 0
• 代码随想录算法训练营第九天| 28. 实现 strStr() 459.重复的子字符串 字符串总...

  28. 实现 strStr() #1 自己看到题目的第一想法 暴力解法。时间复杂度为n*m #2 看完代码随...

  小雨_dea7阅读 105评论 0赞 0
• 算法训练第九天|28. 实现 strStr() 、459.重复的子字符串

  字符串|28. 实现 strStr() 、459.重复的子字符串 28. 实现 strStr()[https://...

  编民不让王公阅读 89评论 0赞 0
• 代码随想录算法训练营第十一天｜20. 有效的括号、1047. 删除字符串中的所有相邻重复项、1...

  20. 有效的括号 题目链接：https://leetcode.cn/problems/valid-parenth...

  Jenny_yq阅读 54评论 0赞 0