KMP 自动机

标签：自动机 复杂度 KMP delta mathcal pi

相当于 \(\pi\) 函数（KMP 中的 next 数组）的扩展。

\(\delta(i,c)\) 表示在 KMP 匹配过程中当模式串指针在 \(i\) ，接受字符 \(c\) 后模式串指针所处的位置。
则 KMP 过程中模式串指针可以被描述为 \(\delta(0,s[1]),\delta(\delta(1,s[1]),s[2]),\cdots\)

借助 KMP 自动机，我们可以将单次转移时间由均摊 \(\mathcal O(1)\) 变为严格 \(\mathcal O(1)\)。可以在当基于均摊复杂度的 KMP 转移无法保证复杂度时（CF808G）作为替代品。

为了方便在模式串被完全匹配时转移，常在最后加入一个不在字符集中的字符 \(\#\) （建议设为 \0）

考虑构建 KMP 自动机。
一个暴力的做法是利用 \(\pi\) 函数暴力跳，然而复杂度最坏是 \(\mathcal O(n^2|\Sigma|)\)
考虑到当跳到 \(\pi[i]\) 时，后面的过程已被求解 \(\delta(\pi[i],c)\) 时所重复。所以只需要跳一次即可。

\[\delta(i,c)=\begin{cases} i+1 &s[i+1]=c \\ 0 &s[1]\not=c\land i=0 \\ \delta(\pi[i],c) &\mathrm{Otherwise} \end{cases}\]

时空复杂度 \(\mathcal O(n|\Sigma|)\)。

标签：自动机,复杂度,KMP,delta,mathcal,pi
From： https://www.cnblogs.com/pref-ctrl27/p/16992644.html