suffix automaton

Suffix automaton

Deterministic acyclic finite state automaton，也叫directed acyclic word graph(DAWG)，是一个识别若干字串的无环DFA。识别若干字串的所有DAWG中，存在唯一一个状态数最少的DAWG，称作minimal DAWG，即识别这个字串集的DFA。

DAWG在有些文献中也指识别一个字串的所有后缀的自动机，这种用法有个更常见的名称：suffix automaton，此时该自动机可以看做是字串所有后缀的DAWG。