论文标题
从线性时间中推断出从位置堆的弦
Inferring Strings from Position Heaps in Linear Time
论文作者
论文摘要
位置堆是用于字符串匹配问题的文本字符串的索引结构。它们是根的树，其边缘和节点分别被标记和编号。本文涉及位置堆构造的反问题的变体，并为这些问题提供线性时间算法。基本问题是要从带有标记的边缘和编号节点的根树上还原文本字符串。在变体问题中，输入树可能会错过边缘标签或节点编号，我们也必须还原。
Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This paper is concerned with variants of the inverse problem of position heap construction and gives linear-time algorithms for those problems. The basic problem is to restore a text string from a rooted tree with labeled edges and numbered nodes. In the variant problems, the input trees may miss edge labels or node numbers which we must restore as well.
