Detecting regularities on grammar-compressed strings
From MaRDI portal
Publication:2514148
DOI10.1016/j.ic.2014.09.009zbMath1312.68238OpenAlexW1982763290MaRDI QIDQ2514148
Kazuyuki Narisawa, Wataru Matsubara, Kouji Shimohira, Masayuki Takeda, Hideo Bannai, Ayumi Shinohara, Shunsuke Inenaga, Tomohiro I.
Publication date: 30 January 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.009
Related Items (6)
Computing longest palindromic substring after single-character or block-wise edits ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Faster Lyndon factorization algorithms for SLP and LZ78 compressed text ⋮ Finger search in grammar-compressed strings ⋮ A Space-Optimal Grammar Compression. ⋮ Balancing straight-line programs for strings and trees
Cites Work
- Unnamed Item
- Unnamed Item
- An efficient algorithm to test square-freeness of strings compressed by straight-line programs
- Parallel detection of all palindromes in a string
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Repetitions in strings: algorithms and combinatorics
- Searching for gapped palindromes
- Efficient parallel algorithms to test square-freeness and factorize strings
- Detecting leftmost maximal periodicities
- An O(n log n) algorithm for finding all repetitions in a string
- ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
- Processing Compressed Texts: A Tractability Border
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
This page was built for publication: Detecting regularities on grammar-compressed strings
