一句话结论
next[i] 是模式串前 i+1 个字符中最长的相等真前缀与真后缀长度,也就是前缀函数 π(i)。它回答的是「失配时已匹配部分还有多长可以复用」。
为什么(原理)
朴素匹配失配时整体右移一位,丢掉了已匹配的信息。若已匹配部分的前缀与后缀相同,这段后缀必然是下一轮的前缀,右移「已匹配长度 − π(已匹配长度−1)」位即可跳过无效比较。
以 ABABACA 为例逐个前缀求值:
| i | 子串 | 最长相等真前后缀 | π(i) |
|---|---|---|---|
| 0 | A | 无 | 0 |
| 1 | AB | 无 | 0 |
| 2 | ABA | A | 1 |
| 3 | ABAB | AB | 2 |
| 4 | ABABA | ABA | 3 |
| 5 | ABABAC | 无 | 0 |
| 6 | ABABACA | A | 1 |
怎么做(命令与配置)
| |
验证方式与预期输出
| |
两条断言都过才算对;AAAA 专挑「只写 if 不写 while」的错误。
踩坑
- 不少教材的
next是 π 左移一位再减 1(即[-1, ...]),与 π 不是同一套定义,混用会在j = next[j]处打转。 - 索引语义要统一:
pi[i]表示长度还是下标,混了就差一位。
延伸思考
π 数组本质是「字符串与自身的相似度」,与 Z 函数可互转,也是很多题用哈希替代 KMP 的底气。