字符串的子串定位称为模式匹配，模式匹配可以有多种方法。简单的算法可以使用两重嵌套循环，时间复杂度为母串与子串长度的乘积。而KMP算法相对来说在时间复杂度上要好得多，为母串与子串长度的和。但其算符比较难以理解。
在KMP算法中，使用到了一个next数组。这个数组就是在比较失配时母串指针不必回溯，而子串指针移动相应位置即可。我们给出书中next数组的算式表示以及算法，请你实现之。
图1：next数组的算式表示
图2：next数组的算法表示
2069: 算法4-7：KMP算法中的模式串移动数组
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $25$ | 正确数量 | $17$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 字符串 |
Description
Input
一个模式串，仅由英文小写字母组成。长度不大于100。
Output
输出模式串对应的移动数组next。每个整数后跟一个空格。
Sample Input复制
abaabcac
Sample Output复制
0 1 1 2 2 3 1 2
提示
提示：
数据结构与以前相同，只用字符数组即可，只要调用上述函数即可。
总结：
KMP算法在字符串模式匹配算法中比较高效，具体KMP算法将在以后介绍。
参考代码：
推荐代码 查看2069 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$0 $ms] | 大喵-sama | 899720 | 2022-10-10 13:08:54 |
| 内存最少[$944 $KB] | 范晋豪@信息与计算科学142 | 152691 | 2017-11-16 15:10:14 |
| 第一AC | 范晋豪@信息与计算科学142 | 152690 | 2017-11-16 15:10:14 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 152690 | 2017-11-16 15:10:14 |
赛题来源/所属竞赛 数据结构高分笔记 数据结构高分笔记
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1300 | 《 2019春季ACM/NOI高级算法集训班》训练二：字符串 | 2019-03-09 14:00:00 | 请登录 |