COUNTING SUBWORDS USING A TRIE AUTOMATON
Hamed Alazemi, Anton Černý · International Journal of Foundations of Computer Science · 2011
We use the concept of trie (prefix tree) representation of a prefix-closed finite language L to design a simple nondeterministic automaton. Each computation of this trie automaton corresponds to a subword occurrence of a word from L in the input word. The matrix representation of the trie automaton leads to a fairly general extension of the original concept of the Parikh matrix from [7].