A linear-time algorithm for the bidirectional construction of suffix trees, which are the most basic index structures used in string processing, is presented in this paper.

An introduction of the main concept--the equivalence class and its properties--begins the paper. Inenaga then explains that the suffix tree is composed of three elements: the set of nodes consisting of the longest members in the equivalent class for the substrings, the set of forward edges connecting the nodes that have common prefixes, and the set of the suffix links connecting nodes that have common suffixes. The paper goes on to introduce the modified suffix tree structure, which is based on an alternative definition of the equivalence class.

The method for the right extension operation, for the construction of suffix trees, is introduced first. Using the longest repeated suffix, the explicit nodes that must be inserted into the original suffix tree can be identified during the right expansion procedure. From Lemma 6, a constant cost procedure for seeking the insertion position is derived. For the left extension operation, the longest repeated prefix, similar to the longest repeated suffix in the right extension operation, is introduced. The paper then presents the procedure for locating the positions for inserting the explicit substrings, which takes constructor time asymptotically.

Finally, the paper shows the influence on the longest repeated suffix (prefix) when the suffix tree is left (right) extended. This leads to the conclusion that the approach presented for the bidirectional construction of suffix trees is a linear-time algorithm.