一、串

image-20210727005353732

定义

image-20210727005406740

串V.S线性表

image-20210727005523561

基本操作

image-20210727005607107

比较操作

image-20210727005635750

字符集编码

image-20210727005701467

总结

image-20210727005742561

二、存储结构

image-20210727005758794

顺序存储与堆分配存储

image-20210727005855765
image-20210727005924608

方案二的字符串长度不可以超过255

块链存储

image-20210727005953465

基本操作的实现

image-20210727010016555
image-20210727010029230
image-20210727010038986
image-20210727010051797
image-20210727010105881

三、模式匹配

image-20200803220247955

朴素模式匹配算法

image-20200803221038452
image-20200803224601338
image-20200803231428235

性能分析

最好时间复杂度

image-20200803231735244

最坏时间复杂度

image-20200803232029485

思想总结

image-20200803232154853四、KMP 算法

简单模式匹配的缺点

image-20210727010646197

改进思想

image-20210727010709758

情况一

image-20210727010730593
image-20210727010746569
image-20210727010759979

情况二

image-20200804224917143

情况三：

image-20210727010926790

4这里有可能多比较一次：因为4和6已经不等，但是1和6相同，这里仍会期待1和6相同，再进行一次比较，所以这里它并不是最优的算法，但是相比于朴素模式匹配，它还是少对比了两次

image-20210727010937811

同理j指向3时少对比1次

总结：

image-20210727010955129

具体代码实现

image-20210727011012022

求next数组

image-20210727011116270
image-20210727011214643
image-20210727011236014

代码实现求next数组

image-20210727011246482

回顾总结

image-20210727011258409

四、KMP 算法

简单模式匹配的缺点

image-20210727010646197

改进思想

image-20210727010709758

情况一

image-20210727010730593
image-20210727010746569
image-20210727010759979

情况二

image-20200804224917143

情况三：

image-20210727010926790

4这里有可能多比较一次：因为4和6已经不等，但是1和6相同，这里仍会期待1和6相同，再进行一次比较，所以这里它并不是最优的算法，但是相比于朴素模式匹配，它还是少对比了两次

image-20210727010937811

同理j指向3时少对比1次

总结：

image-20210727010955129

具体代码实现

image-20210727011012022

求next数组

image-20210727011116270
image-20210727011214643
image-20210727011236014

代码实现求next数组

image-20210727011246482

回顾总结

image-20210727011258409

五、KMP 算法的优化

KMP算法存在的问题

image-20210727011317097

例子2：

image-20210727011359659

总结

image-20210727011418148