字符串

学习说明

本章可能在选择题中出现，掌握 KMP 算法的思想，能够手工模拟 KMP 过程即可。

串是由零个或多个字符组成的有限序列；与一般线性表相比，题目更关心字符比较、子串定位和模式匹配。学习时不要只背 next 数组：先分清主串是被搜索对象、模式串是待匹配对象，再理解失配后为什么可以复用已比较字符的前后缀信息。

手工模拟 KMP 时，建议每一步都写出主串指针、模式串指针和本次失配后的回退位置。KMP 的关键不是让两个指针都回退，而是主串中已经确认无须重查的部分保持向前；next 或 nextval 的具体下标约定随教材而异，必须始终使用同一套定义验证样例。