串定义
- 字符串简称串
- 由零个或多个字符组成的有限序列，记为
， - 空串用空集
表示 - 串中任意多个连续字符子序列称作子串，包含子串的叫主串
- 子串的位置指子串第一个字符在主串中的位置
- 两个串相等，指长度相等且对应位置字符相等
- 串的逻辑结构和线性表类似，但串的数据对象仅为字符，且串的操作对象一般是子串。
串的存储结构
- 定长顺序存储：一般利用定长数组实现
- 堆分配动态存储：利用malloc和free函数
- 块链存储：每个结点可以放一个字符，也可以放多个。例如结点大小可以是4，最后一个结点如果不满4个字符用#补齐。
串的模式匹配
子串的定位称作串的模式匹配，即求子串（模式串）在主串中的位置
朴素模式匹配算法
即暴力搜索，假设主串大小
KMP算法
核心步骤
- 设主串为
，模式串为 - 当主串的第i个字符和模式串的第j个字符失配，跳到子串的第
字符位置，与主串第i个位置进行继续比较（这里i和j都是从1开始）
next数组人工算法
，当 。直观意思是 与 比较，本质就是 与 比较 ，当 集合非空。这里的 中元素 满足 ，且 的前 个字符和后 个字符自匹配 ，其他情况
next数组机器算法
使用类似于数学归纳法的思想递推
- 假设已知
，则 ？ - 由
，显然 的前k-1子串和后k-1子串匹配 - 比较
和 - 如果相等，说明
的前k子串和后k子串匹配，则 - 如果不相等，令
，如果 则继续比较 和 ，以此类推；如果 则 （理解成 的前0子串和后0子串匹配） - 不相等的情况是KMP算法生涩的地方，可以直接记住，也可以根据例子来进行理解
- 如果相等，说明
- 由
KMP算法原理
举例帮助理解：主串cabcabcac，子串abcac
- c和a不匹配，即子串第
个位置不匹配， ，即主串的第 个和子串的第 个比较，也就是主串的第 个和子串第 个比较 - 主串的abca和子串abca匹配，但主串第
的b和子串第 的c不匹配 ，则主串的第 个b和子串第 的b进行比较 - 完成匹配
KMP算法进一步优化
注意到前面核心步骤处：
- 设主串为
，模式串为 - 当主串的第i个字符和模式串的第j个字符失配，跳到子串的第
字符位置，与主串第i个位置进行继续比较（这里i和j都是从1开始）
那么
- 若
，必有 ，失配是必然 - 因此为了避免
，将 反复修正为 ，直至 - 修正后的next记作nextval，可以从j=1开始修正，这样每次只需要修正一次
即可
