Constructing Factor Oracles

A factor oracle is a data structure for weak factor recognition. It is an automaton built on a string $p$ of length $m$ that is acyclic, recognizes at least all factors of $p$, has $m+1$ states which are all final, and has $m$ to $2m-1$ transitions. In this paper, we give two alternative algorithms ... View More