Editing String-searching algorithm (section)

=== Index methods ===
Faster search algorithms preprocess the text. After building a [[substring index]], for example a [[suffix tree]] or [[suffix array]], the occurrences of a pattern can be found quickly. As an example, a suffix tree can be built in <math>\Theta(n)</math> time, and all <math>z</math> occurrences of a pattern can be found in <math>O(m)</math> time under the assumption that the alphabet has a constant size and all inner nodes in the suffix tree know what leaves are underneath them. The latter can be accomplished by running a [[Depth-first search|DFS algorithm]] from the root of the suffix tree.