Ganguly, Arnab ;
Shah, Rahul ;
Thankachan, Sharma V.
Structural Pattern Matching  Succinctly
Abstract
Let T be a text of length n containing characters from an alphabet \Sigma, which is the union of two disjoint sets: \Sigma_s containing static characters (scharacters) and \Sigma_p containing parameterized characters (pcharacters).
Each character in \Sigma_p has an associated complementary character from \Sigma_p.
A pattern P (also over \Sigma) matches an equallength substring $S$ of T iff the scharacters match exactly, there exists a onetoone function that renames the pcharacters in S to the pcharacters in P, and if a pcharacter x is renamed to another pcharacter 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 \Theta(n\log n) bits of space, and can find all occ occurrences in time O(P\log \sigma+ occ), where \sigma = \Sigma.
In this paper, we present the first succinct index for this problem, which occupies n \log \sigma + O(n) bits and offers O(P\log\sigma+ occ\cdot \log n \log\sigma) query time.
BibTeX  Entry
@InProceedings{ganguly_et_al:LIPIcs:2017:8256,
author = {Arnab Ganguly and Rahul Shah and Sharma V. Thankachan},
title = {{Structural Pattern Matching  Succinctly}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {35:135:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8256},
URN = {urn:nbn:de:0030drops82566},
doi = {10.4230/LIPIcs.ISAAC.2017.35},
annote = {Keywords: Parameterized Pattern Matching, Suffix tree, BurrowsWheeler Transform, Wavelet Tree, Fullyfunctional succinct tree}
}
07.12.2017
Keywords: 

Parameterized Pattern Matching, Suffix tree, BurrowsWheeler Transform, Wavelet Tree, Fullyfunctional succinct tree 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 