Structural Pattern Matching - Succinctly

Keywords

Burrows-wheeler transform; Fully-functional succinct tree; Parameterized pattern matching; Suffix tree; Wavelet tree

Abstract

Let T be a text of length n containing characters from an alphabet ∑, which is the union of two disjoint sets: ∑s containing static characters (s-characters) and ∑p containing parameterized characters (p-characters). Each character in ∑p has an associated complementary character from p. A pattern P (also over ∑) matches an equal-length substring S of T iff the s-characters match exactly, there exists a one-To-one function that renames the p-characters in S to the p-characters in P, and if a p-character x is renamed to another p-character y then the complement of x is renamed to the complement of y. The task is to find the starting positions (occurrences) of all such substrings S. Previous indexing solution [Shibuya, SWAT 2000], known as Structural Suffix Tree, requires (n log n) bits of space, and can find all occ occurrences in time O(|P| log σ+occ), where σ = |∑|. In this paper, we present the first succinct index for this problem, which occupies n log σ + O(n) bits and offers O(|P| log σ + occ · log n log σ) query time.

Publication Date

12-1-2017

Publication Title

Leibniz International Proceedings in Informatics, LIPIcs

Volume

92

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.4230/LIPIcs.ISAAC.2017.35

Socpus ID

85038577673 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85038577673

This document is currently not available here.

Share

COinS