Question

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).

Answer 1

For number 2, I think you would just check if the DFA ever enters an accept state, instead of just checking if it ends in an accept state. So just run the algorithm as normal, but halt and accept as soon as the automation transitions to an accept state, instead of waiting until the end of the input. (The number of times the automation enters an accept state is the number of substrings of the language contained in the input string)

Not sure about number 1 though. I am not sure what operations (if any) minimal DFAs are closed under, but I think the number of operations required by a slightly modified version of Hopcraft's algorithm would be proportional to the size of a word you add via union.