Construction
Build trie. Post-order merge: two nodes equivalent iff same isEnd + same children. Merge equivalence classes.
Advertisement
Perfect hashing
Number states in traversal order. States describe minimal automaton for word set.
Advertisement
Suffix DAWG
DAWG of all suffixes = suffix automaton. Same underlying idea, applied to suffixes of single string.