【代码随想录】--字符串个人笔记
字符串理解
可以把字符串当成一个特殊的数组,该数组最后一个非0元素为\\0
,代表字符串到此结束。
例题
1、剑指Offer58-II.左旋转字符串
题目链接:https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.md
局部翻转+全部翻转:
将整个字符串看成由前k个和后(n-k)个子串组成,若不考虑子串内元素先序关系,左旋转其实把这俩子串位置互换了。俩子串自己先翻转一次,然后再整体翻转,就实现了俩子串的位置互换,需要注意的是,得先进行子串的翻转,不然最后其实是后k个字符为一个子串,就不符合题意了。
KMP算法
引入
模式串第一次在主串中出现朴素算法
移动模式串
理解
模式串中存在某子串重复出现的情况
KMP算法相较暴力匹配,减少了重复匹配与待查字符串除了后几位不同子串的开销。其实就是因为模式串中某子串重复出现了,失配后可以减少回溯。
可以从以下任一角度来理解:
- 知乎博主的有限状态机动角度来看,动图很直观了:https://zhuanlan.zhihu.com/p/83334559
- Carl哥的,也是数据结构(C语言)版的实现方式,前缀表。