字符串-AC自动机

· · 算法·理论

自动机是什么

这是一个困扰了我很久的问题，自从小学开始学OI以来就常常听大佬们讨论的问题，却从来没有认真了解过

简单来说，自动机是一个对信号序列进行判定的数学模型

一般我们所常说的“自动机”是指 确定有限状态自动机（DFA）

其作用就是识别字符串，一个自动机A，如果能识别（接受）字符串S，那么A(S)=True，否则A(S)=False

当一个 DFA 读入一个字符串时，从初始状态起按照转移函数一个一个字符地转移。如果读入完一个字符串的所有字符后位于一个接受状态，那么我们称这个 DFA 接受 这个字符串，反之我们称这个 DFA 不接受 这个字符串

参考：OI-WIKI-自动机

AC自动机

参考：OI-WIKI-AC自动机