Prague Stringology Conference 2011
Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Inferring Strings from Suffix Trees and Links on a Binary Alphabet
| Abstract: |
| A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: Given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. By introducing new characterizations of suffix trees, we show that the reverse engineering problem on suffix trees on a binary alphabet can be solved in linear time in the input size. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |