Computing all subtree repeats in ordered trees

Michalis Christou (1) , Maxime Crochemore (1, 2) , Tomas Flouri (3) , Costas Iliopoulos (1) , Jan Janousek (3) , Borivoj Melichar (3) , Solon Pissis (1, 4)

1 Informatics
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 TCS-CTU - Department of Theoretical Computer Science
4 DCS - Department of Computer Science

We consider the problem of computing all subtree repeats in a given labeled ordered tree. We first transform the tree to a string representing its postfix notation, and then present an algorithm based on the bottom-up technique to solve it. The proposed algorithm consists of two phases: the preprocessing phase and the phase where all subtree repeats are computed. The linear time and space complexity of the proposed algorithm are important parts of its quality.

Mots clés: Algorithms; Trees; Strings; Subtree repeats

Domaines: Algorithme et structure de données [cs.DS]

Michalis Christou, Maxime Crochemore, Tomas Flouri, Costas Iliopoulos, Jan Janousek, et al.. Computing all subtree repeats in ordered trees. Information Processing Letters, 2012, 112 (24), pp.958-962. ⟨10.1016/j.ipl.2012.09.001⟩. ⟨hal-00836959⟩