Inferring strings from position heaps in linear time

09/26/2022
by   Koshiro Kumagai, et al.
0

Position heaps are index structures of text strings used for the exact string matching problem. They are rooted trees whose nodes and edges are both labeled. 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 nodes and edges. The input trees may miss edge labels or node labels in the variant problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset