How can we add new words to DFA, maintaining minimality?
Maybe, you can advise some completely different approach to solve the following problem:
A program must process two types of queries:
- Add new word to the language.
- Check if some word of the language occurs in the input string as a substring.
Time and space complexity should be as low as possible.
The only solution that I know so far is to rebuild an automaton from scratch every time, using Aho-Corasick algorithm, but, you know, it's really-really inefficient.
I've performed some search on Internet and found some papers like "Incremental Construction of Minimal Acyclic Finite-State Automata", but, unfortunately, algorithm described there produces and maintains just a minimal trie (not a complete FSM with suffix links, like an automaton produced by Aho-Corasick algo).