以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

串

ADT

定义和特点

术语

统一约定：

联系：在i+k长度的前缀中，长度为k的后缀

任何串，也是他自身的子串，前缀，后缀，长度严格小于原串的子串，前缀，后缀，也成为了真子串，真前缀，真后缀

接口定义

模式匹配

问题与需求

算法评测

蛮力匹配

构思

版本一

版本二

复杂度分析

但是就期望而言，对于日常使用，往往可以每一个位置都达到o（1），总共累计不过线性O（n）复杂度

我们不满足于次，想要把期望抹掉，好消息是这类算法的确存在，比如下面的知名的KMP

KMP算法:记忆法

阐述

蛮力为何低效

不变性

记忆力

预知力

查询表

制表备查

主算法

实例

理解Next[]表

快速移动

避免回溯

t越小，对应的位移越大，反之，对应的位移越小，而位移量更小，就意味着更安全，这也暗示了另一个不变性，也就是由KMP舍弃的哪些位置，的确是不值得对齐的

通配哨兵

当j<0时，通过通配的哨兵结点，使得T[i] == T[j] 必然成功，从而使模板表位置回到第一位

构造Next[]表

递推

算法

显而易见，该过程也就是next自己与自己逐一比对的过程，（哨兵使得算法鲁棒性良好）我们可以通过修改KMP的框架简要得出模板表的代码

实现

int* buildNext ( char* P ) { //构造模式串P的next表
0002    size_t m = strlen ( P ), j = 0; //“主”串指针
0003    int* N = new int[m]; //next表
0004    int t = N[0] = -1; //模式串指针
0005    while ( j < m - 1 )
0006       if ( 0 > t || P[j] == P[t] ) { //匹配
0007          j ++; t ++;
0008          N[j] = t; //此句可改进...
0009       } else //失配
0010          t = N[t];
0011    return N;
0012 }