前言
字符串学了三天,七道题。初窥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[ ]求出来,然后根据题目要求,利用和前缀表的关系求解
最后
下一站,栈与队列!