When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.35
URN: urn:nbn:de:0030-drops-82566
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8256/
 Go to the corresponding LIPIcs Volume Portal

### Structural Pattern Matching - Succinctly

 pdf-format:

### 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 (s-characters) and \Sigma_p containing parameterized characters (p-characters). Each character in \Sigma_p has an associated complementary character from \Sigma_p. A pattern P (also over \Sigma) 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 \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:1--35:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-054-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{92},
editor =	{Yoshio Okamoto and Takeshi Tokuyama},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},