Computing longest palindromic substring after single-character or block-wise edits
From MaRDI portal
Publication:2227497
DOI10.1016/j.tcs.2021.01.014zbMath1502.68378arXiv1901.10722OpenAlexW3120084479MaRDI QIDQ2227497
Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Hideo Bannai, Mitsuru Funakoshi
Publication date: 15 February 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1901.10722
Related Items (6)
Minimal unique palindromic substrings after single-character substitution ⋮ The heaviest induced ancestors problem: better data structures and applications ⋮ Shortest unique palindromic substring queries in semi-dynamic settings ⋮ Tight bound for the number of distinct palindromes in a tree ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Data structures for computing unique palindromes in static and non-static strings
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Counting distinct palindromes in a word in linear time
- The level ancestor problem simplified
- Parallel detection of all palindromes in a string
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Searching for gapped palindromes
- Finding level-ancestors in trees
- EERTREE: an efficient data structure for processing palindromes in strings
- Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets
- Finding approximate palindromes in strings
- On-line construction of suffix trees
- Detecting regularities on grammar-compressed strings
- Computing Longest Single-arm-gapped Palindromes in a String
- Suffix Arrays: A New Method for On-Line String Searches
- Fast Algorithms for Finding Nearest Common Ancestors
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- Algorithms on Strings, Trees and Sequences
- Efficient algorithms for Lempel-Ziv encoding
- Repetition Detection in a Dynamic String
- Faster queries for longest substring palindrome after block edit
- Longest substring palindrome after edit
- Longest Lyndon Substring After Edit
- The Heaviest Induced Ancestors Problem Revisited
- Longest Common Factor After One Edit Operation
- Pal k is Linear Recognizable Online
- Dynamic LCA Queries on Trees
- Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
- Palindromic Decompositions with Gaps and Errors
- On the sorting-complexity of suffix tree construction
This page was built for publication: Computing longest palindromic substring after single-character or block-wise edits