Inferring Strings from Suffix Trees and Links on a Binary Alphabet
Inferring Strings from Suffix Trees and Links on a Binary Alphabet
复制标题
从后缀树和二进制字母表上的链接推断字符串
DOI：
10.1016/j.dam.2013.02.033
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Tomohiro I;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
后缀树为我们提供给定字符串的线性空间全文索引，是字符串处理和信息检索的基本数据结构。本文考虑后缀树上的逆向工程问题：给定一棵无标记有序根树T和一个节点到节点的转移函数f，推导出一个字符串，其后缀树及其内部节点的后缀链接分别同构于T和f。此外，我们还考虑枚举问题，其中我们枚举与输入树和链接相对应的所有字符串。通过引入后缀树的新特征，我们证明了逆向工程问题和二进制字母表上后缀树的枚举问题可以在最优时间内得到解决。
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. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time.