串

串的定义

由0个或多个字符组成的有限序列，n表示字符串长度，n=0的串称为空串

• 子串：串中任意个连续的字符组成的子序列
• 主串：包含子串的串

注意：

1. 位置(位序)从1开始，数组下标从0开始。

2. 空串‘’与空格串‘ ’不同，一个空格占1Byte,8个bit。

3. 串是一种特殊的线性表

串的操作

• 注意比较操作，判断方法是从第一个字符开始往后依次对比

  先出现更大字符的串更大(ASCII编码)，在前缀完全相同时长串更大。

  只有当串完全相同时，串才相等。

串的存储结构

1. 静态数组实现(预先给定数组长度,基本不可变)

   1. 可以立即找到元素位置
   2. 但拓展和收缩很难做到
   3. 具备顺序表的优缺点

2. 动态数组实现(堆分配存储)，使用后需手动free释放。

   ​ 具备链表的优缺点。

串的模式匹配朴素算法

模式串：想尝试在主串中找到的串，未必存在。

与串的定位操作大差不差，代码如下

若模式串长度为m,主串长度为N,

• 则匹配成功的最好时间复杂度为O(m)。
• 匹配失败的最好时间复杂度为O(n)。
• 两种情况的最坏时间复杂度为O()(n-m+1)*m)约等于O(nm)

算法的核心思想

​ 将主串的每一个与模式串长度相同的子串依次与模式串对比，一旦子串与模式串某个对应字符不匹配时，立即放弃当前字串，判断下一个字串。

​ 缺点：当某些子串与模式串能部分匹配时，主串的扫描指针经常回溯导致时间开销大。

K.M.P算法

通过回溯模式串指针，而不是主串指针来减少对比次数，提高查找效率。

如何回溯模式串？通过next数组，它记录了模式串与主串不匹配的时候，模式串从哪里重新匹配

前缀与后缀：

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

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

• 你的目光永远是从左到右看的！

前缀表的记录

这个next数组，本质就是一种前缀表，记录着下标i(包括i)的字符串中，有多大长度的相同前缀后缀

next[i]表示string[i]以前（包括string[i]）最长相等前后缀的长度

前缀表的使用

当string[i]!=str[j]时，令j=table[j-1]

前缀表与next数组

大部分next数组实现基于前缀表的基础，将所有元素-1得出。

• 发生冲突时，寻找发生冲突的前一位，将对应next数组元素+1后寻找，即j=table[j-1]+1

也有部分实现，基于前缀表，将前缀表整体右移动，next[0]=-1得出，这也是408考题做法

• 发生冲突时，寻找发生冲突的位置的next值，即j=next[j]
• 当字符串编号位序为1时，next数组整体+1，显著特点是next[0]=0，next[1]=1

也有部分实现，直接将前缀表作为next数组

• 当冲突时，寻找发生冲突的前一位，即j=table[j-1]