总忘，很痛苦！简单总结一下步骤呃呃呃呃呃呃
求next数组
以字符串abaabc为例。
①虽然不知道发生了什么总之我先填个-1和0在这里
| a | b | a | a | b | c |
|---|---|---|---|---|---|
| -1 | 0 |
②这时已有字符串ab，没有重复的前后缀，于是再写个0
| a | b | a | a | b | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 |
③已有字符串aba，最长相等前后缀a长度是1，写个1
| a | b | a | a | b | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 | 1 |
④已有字符串abaa，最长相等前后缀依旧为a，还是1
| a | b | a | a | b | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 | 1 | 1 |
⑤已有字符串abaab，最长相等前后缀ab，写2
（[a,b]；[ab,ab]；[aba,aab]；[abaa,baab]）
| a | b | a | a | b | c |
|---|---|---|---|---|---|
| -1 | 0 | 0 | 1 | 1 | 2 |
⑥你拥有了一个next数组（视情况给每项+1）！神奇吧！
字符串匹配
以主串Taabaabaabaac和模式串saabaac为例。
①按照之前的方法求出aabaac的next数组
| a | a | b | a | a | c |
|---|---|---|---|---|---|
| -1 | 0 | 1 | 0 | 1 | 2 |
②第一个不匹配的字符c对应的next数组中数值为2
| a | a | b | a | a | a | a | b | a | a | c | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a | a | b | a | a |
所以将s[2]（即字符串s的第三位）和出错的那一位对齐，再次比较
| a | a | b | a | a | {b} | a | a | a | a | c | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a | a | {b} | a | a |
再次对齐
| a | a | b | a | a | b | a | a | {b} | a | a | c |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a | a | {b} | a | a | c |
③成功了耶！信积拉奶！（
拓展&总结
做题特化（指不管原理只管答案）
想要原理的话可以看看如何更好地理解和掌握 KMP 算法? - 知乎
over，希望能帮助到现实主义者的你！（
网友评论