Detecting regularities on grammar-compressed strings

DOI10.1007/978-3-642-40313-2_51MaRDI QIDQ2849944zbMATH OpenOpenAlexFDO

Authors Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara, Tomohiro I

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7067

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Abstract: We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size $n$ that represents a string $s$ of length $N$, our algorithm compute all runs and squares in $s$ in $O(n^{3}h)$ time and $O(n^2)$ space, where $h$ is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in $O(n^{3}h+gnhlogN)$ time and $O(n^2)$ space, where $g$ is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in $O(n^{2}h)$ time and $O(nh(n+lo{g}^{2}N))$ time, respectively.

Recommendations

• Detecting regularities on grammar-compressed strings
• Algorithmics on SLP-compressed strings: a survey
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Fast \(q\)-gram mining on SLP compressed strings

Cited in

(3)

• Finger Search in Grammar-Compressed Strings
• Access, rank, and select in grammar-compressed strings
• Detecting regularities on grammar-compressed strings

This page was built for publication: Detecting regularities on grammar-compressed strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849944)