前置知识：\(\texttt{trie}\) 树。不会的话到这篇博客看看吧。
前置知识：\(\texttt{kmp}\)。不会的话到这篇博客看看吧。
字符串好的题单。下面设所有字符串的大小之和为 \(|\Sigma|\)。
\(\texttt{AC}\) 自动机（也叫 \(\texttt{ACAM}\)）
\(\texttt{ACAM}\) 时为了解决 \(\lceil\) 多个字符串在一个字符串上的匹配 \(\rfloor\) 的问题。设多个字符串为 \(S_1,S_2,\dots,S_n\)，那一个字符串为 \(T\)。
如果暴力 \(\texttt{kmp}\) 的话复杂度为 \(|\Sigma||T|\)，显然会爆炸。
我们把 \(S_1,S_2,\dots,S_n\) 建成一颗 \(\texttt{trie}\) 树。
比如这样，灰色是结尾。
标签：AC,trie,ACAM,texttt,笔记,字符串,自动机 From： https://www.cnblogs.com/HaHeHyt/p/17379227.html