自动机

Definition

一个确定有限状态自动机（DFA）\(M=(Q,\Sigma,\delta,q_0,F)\)由以下五个部分组成：
\(1.\)状态集合\(Q\)
\(2.\)字符集\(\Sigma\)
\(3.\)转移函数\(\delta:Q\times\Sigma\rightarrow Q\)
\(4.\)起始状态\(q_0\in Q\)
\(5.\)接受状态集合\(F\subseteq Q\)
若\(s=a_1\cdots a_n\)是\(\Sigma\)上的一个字符串，则我们称\(M\)接受该字符串当且仅当存在一组状态序列\(f_0,\cdots,f_n\)满足：
\(1.f_0=q_0\)
\(2.\forall i\in[1,n]f_i=\delta(f_{i-1},a_i)\)
\(3.f_n\in F\)

Trie

Trie是接收且仅接受给定字符串集合中的字符串的DFA。

KMP自动机

KMP自动机是一个仅接受以给定字符串\(s\)为后缀的字符串的DFA。
\(Q=\{0,\cdots,|s|\},q_0=0,F=\{|s|\},\delta(i,c)=\begin{cases}i+1&s_{i+1}=c\\0&s_1\ne c\wedge i=0\\\delta(next_i,c)&s_{i+1}\ne c\wedge i>0\end{cases}\)

构建

注意到因为我们已经维护了\(\delta\)，所以可以不用像KMP一样暴力跳\(next\)而可以直接一步到位。做到时间复杂度严格\(O(n|\Sigma|)\)。

for(int i=1,fail=0;i<=n;++i)
{
    fail=delta[fail][s[i]],delta[i-1][s[i]]=i;
    for(int j=0;j<m;++j) delta[i][j]=delta[fail][j];
}

自动机

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12219264.html