力扣字符串

字符串"/>

力扣字符串

前言

字符串学了三天，七道题。初窥kmp，已经感受到算法的博大精深了。

内容

对字符串的操作可以归结为以下几类：

字符串的比较、连接操作（不同编程语言实现方式有所不同）；

涉及子串的操作，比如前缀，后缀等；

字符串间的匹配操作，如 KMP 算法、BM 算法等。

一些注意点 

注意双引号和单引号

当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章 

Go 语言中的字符串和其他高级语言（Java、C#）一样，默认是不可变的（immutable）。字符串不可变有很多好处：

如天生线程安全，大家使用的都是只读对象，无须加锁；

再者，方便内存共享，而不必使用写时复制（Copy On Write）等技术；

字符串 hash 值也只需要制作一份。

修改字符串时，可以将字符串转换为 []byte 进行修改。

[]byte 和 string 可以通过强制类型转换互转。

不要太迷恋于库函数

一些思路

双指针

整体+局部思想

先整体操作，后局部操作；或者先局部操作，再整体操作。

如将整个字符串反转，再将每个单词反转。

构建新的字符串

如复制原字符串str=s+s

kmp算法

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配

什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

初始化

处理前后缀不相同的情况

处理前后缀相同的情况

主要是把前缀表next[ ]求出来,然后根据题目要求，利用和前缀表的关系求解

最后

下一站，栈与队列！