Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Factor oracle
open-in-new
<p>A factor oracle is a <a href="/facts/Finite-state_automaton/GMusWd0a">finite-state automaton</a> that can efficiently search for factors (<a href="/facts/Substring/dM5Rqg6X">substrings</a>) in a body of text. Older techniques, such as <a href="/facts/Suffix_tree/pdQdCxbe">suffix trees</a>, were time-efficient but required significant amounts of memory. Factor oracles, by contrast, can be constructed in linear time and space in an incremental fashion. </p>