Online construction of subsequence automata for multiple texts

We consider a deterministic finite automaton which accepts all subsequences of a set of texts, called subsequence automaton. We show an online algorithm for constructing a subsequence automaton for a set of texts. It runs in O(|Σ|(m+k)+N) time using O(|Σ|m) space, where |Σ| is the size of alphabet, m is the size of the resulting subsequence automaton, k is the number of texts, and N is the total length of texts. It can be used to preprocess a given set S of texts in such a way that for any query ω ∈ Σ*, returns in O(|ω|) time the number of texts in S which contain ω as a subsequence. We also show an upper bound of the size of automaton compared to the minimum automaton