KMP自动机的转移边数是2n？？？

先抱歉标题党qwq请大佬们帮忙看看有没有假

KMP自动机指的是：KMP中预处理 每个位置后添加每个字符转移到的位置，可用于一些 $DP$ 题。

题意：注意到很多转移边都会指回 $0$，认为这些边是平凡的，求非平凡转移边数量上界。

设 $d_i$ 为 $i$ 在失配树上的深度，$c_i$ 表示 $i$ 的转移边数量。由于 $n$ 自身不能向后添加字符，故有 $c_n\le d_n-1$。

对于 $0\le i<n$，有显然结论：$i+1$ 的祖先（$0$ 除外）减一均为 $i$ 的祖先。因此我们将 $i$ 的祖先按照下一个字符分类（每一类对应一条转移边），只有一类被全部继承给 $i+1$，其他类都被全部抛弃了。$i+1$ 自己还会凭空生出一个 $0$ 作为祖先，因此有 $c_i-1\le d_i-d_{i+1}+1$（每一类至少有一个元素）。

综上，答案为 $\sum_{i=0}^{n}c_i\le (d_n-1)+\sum_{i=0}^{n-1}d_{i}-d_{i+1}+2\le 2n+d_n-1+d_0-d_n=2n$。