一种极致简化、好写好记的 1-index KMP 写法

· · 算法·理论

提供一种极致简化好写好记的 1-index KMP 写法。

int a[2000010], nxt[2000010];
void KMP(int n){
    nxt[0] = -1;
    for(int i = 1; i <= n; i ++){
        nxt[i] = i;
        do nxt[i] = nxt[nxt[i] - 1] + 1;
        while(nxt[i] && a[i] != a[nxt[i]]);
    }
}
$\mathrm{nxt}_i$ 在每一轮表示的是待匹配的字符的位置，因为是 1-index，所以 border 长度恰好就是要匹配的字符的下标。 若失配，将上一轮匹配失败带来的 $+1$ 去掉，取下一个 border。 考虑边界，显然我们对于 $i \ge 1$ 有 $\mathrm{nxt}_i+1 > 0$，因此循环条件不会触发 $\mathrm{nxt}_i\ne 0$。 边界就是 $\mathrm{nxt}_i - 1$ 在上一轮取到 $0$，下一轮 $\mathrm{nxt}_i\gets \mathrm{nxt}_0+1=0$，这种情况不需要继续匹配，直接退出即可。