王道数据结构课代表 - 考研数据结构 第四章 串-KMP(看毛片算法) 究极精华总结笔记（C版本）

王道数据结构课代表 - 考研数据结构 第四章 串-KMP(看毛片算法) 究极精华总结笔记（C版本）

本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！
关于对 “串” 章节知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研数据结构“串”章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。

精准控时：
如果不实际 *** 作代码，只是粗略过一下知识点，需花费 30 分钟左右过一遍
这个30分钟是我在后期冲刺复习多次尝试的时间，可以让我很好的在后期时间紧张的阶段下，合理分配复习时间；
但是刚开始看这份博客的读者也许会因为知识点陌生、笔记结构不太了解，花费许多时间，这都是正常的。
重点！！！学习一定要多总结多复习！重复、重复、再重复！！！

食用说明书：
第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。
所以再第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片对应的知识点以及自己的思考。
最后第三遍，查漏补缺。
所以 ，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！
请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！
注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

---

第4章 串

文章目录

第4章 串

4.1 串的定义和实现

4.1.1 串的定义4.1.2 串的存储结构

1、串的顺序存储2、串的链式存储3、串的基本 *** 作4、4.1.2小结 4.2 串的模式匹配

4.2.1 简单的模式匹配算法

1、具体代码2、分析算法性能3、4.2.1小结 4.2.2 改进的模式匹配算法——KMP算法

1、算法思想2、初步代码3、常考：求模式串的next数组

例子方法总结练习 4、KMP算法性能分析5、4.2.2小结 4.2.3 KMP的进一步优化 —— nextval数组

算法总结

4.1 串的定义和实现

4.1.1 串的定义

子串：串中任意的连续的字符（空串也可以是子串）主串位置：位序

串也是线性表（数据类型有限制）

4.1.2 串的存储结构 1、串的顺序存储

2、串的链式存储

链式存储缺点：存储密度低你会发现为了存储char类型的数据，反而还搭配了一个占据空间更大的指针，无疑是浪费！改进：提高结点里数据域所能表示的数据量

3、串的基本 *** 作

4、4.1.2小结

---

4.2 串的模式匹配 4.2.1 简单的模式匹配算法

模式匹配：在主串中找到与模式串相同的子串模式串与子串不是一个概念，未必在主串中存在下图中的红字在描述上不是那么准确（有误会），不过大致意思要明白

朴素模式匹配算法：暴力匹配

1、具体代码

2、分析算法性能

算法性能分析在图中已经介绍的很清楚了，这里不再解释了

3、4.2.1小结

---

4.2.2 改进的模式匹配算法——KMP算法 1、算法思想

主要思想：当模式匹配失败时，该回溯到哪里呢？看下图中“关键”指出的next[]数组

2、初步代码

3、常考：求模式串的next数组

本节探讨：手算方式求模式串的next数组 例子

方法总结

后缀指的是主串，前缀指的是模式串前缀后缀都是指一个串里截取部分串（连续）出来，只是前缀必须有第一个字符，不能有最后一个字符后缀同理其实这种方法总结太麻烦了，不如直接自己看，next[i]选择能匹配最多字符的位置例如next[7]可以等于5，也可以等于3，但是优先选择3注意注意注意！

后缀的尾对前缀的头，后缀在上前缀在下

练习

next[1]一定为0，next[2]一定为1模式串第一个元素不匹配，next[1]为0就是说：主串直接匹配下一个模式串第二个元素不匹配，只能从一个重新匹配了模式串第三个元素不匹配，这个时候才考虑从第一个还是第二个开始匹配所以，做题直接考虑第三个

4、KMP算法性能分析

O（m）：模式串的长度mO（n）：主串的长度n

5、4.2.2小结

KMP的关键思想：主串的扫描指针i不回溯（i一直+1），模式串的扫描指针j回溯KMP还存在缺陷

---

4.2.3 KMP的进一步优化 —— nextval数组

当主串的第4个字符和模式串的第4个字符发生不匹配时next[4]=1，可是模式串1位置和4位置一样都是g，还是和l不匹配，这样就多余一次

算法总结

上面图片中的案例解析：

步骤原因 *** 作1nextva[1] = 02next[2]==1 看S[1] && a!=bnextva[2] = next[2] =13next[3]1 看S[1] && aanextva[3] = nextva[1]4next[4]2 看S[2] && bbnextva[4] = nextva[2]5next[5]3 看S[3] && aanextva[5] = nextva[3]6next[6]=4 看S[4] && b!=anextva[6] = next[6] = 4

---

考验人加油！！！