Details

Autor(en) / Beteiligte

• AYALA-RINCON, Mauricio
• CONEJO, Paulo D

Titel

A linear time lower bound on mccreight and general updating algorithms for suffix trees

Ist Teil von

• Algorithmica, 2003-11, Vol.37 (3), p.233-241

Ort / Verlag

New York, NY: Springer

Erscheinungsjahr

2003

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Suffix trees are the fundamental data structure of combinatorial pattern matching on words. Suffix trees have been used in order to give optimal solutions to a great variety of problems on static words, but for practical situations, such as in a text editor, where the incremental changes of the text make dynamic updating of the corresponding suffix trees necessary, this data structure alone has not been used with success. We prove that, for dynamic modifications of order O(1) of words of length n, any suffix tree updating algorithm, such as the ones proposed by McCreight, requires O(n) worst-case running time, as for the full reconstruction of the suffix tree. Consequently, we argue that this data structure alone is not appropriate for the solution of combinatorial problems on words that change dynamically.