Computing longest palindromic substring after single-character or block-wise edits
From MaRDI portal
Publication:2227497
DOI10.1016/J.TCS.2021.01.014zbMATH Open1502.68378arXiv1901.10722OpenAlexW3120084479MaRDI QIDQ2227497FDOQ2227497
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)
Abstract: Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O(n) time by Manacher's algorithm [J. ACM '75]. In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LPSs in O(log (min {sigma, log n})) time after a single character substitution, insertion, or deletion, where sigma denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O(n) time and space for preprocessing, and answers the length of the LPSs in O(ell + log log n) time, after an existing substring in T is replaced by a string of arbitrary length ell.
Full work available at URL: https://arxiv.org/abs/1901.10722
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- EERTREE: an efficient data structure for processing palindromes in strings
- Algorithms on Strings, Trees and Sequences
- The level ancestor problem simplified
- Suffix Arrays: A New Method for On-Line String Searches
- Finding level-ancestors in trees
- On-line construction of suffix trees
- Fast Algorithms for Finding Nearest Common Ancestors
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Dynamic LCA Queries on Trees
- Searching for gapped palindromes
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- Counting distinct palindromes in a word in linear time
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Parallel detection of all palindromes in a string
- On the sorting-complexity of suffix tree construction
- Finding approximate palindromes in strings
- Efficient algorithms for Lempel-Ziv encoding
- Detecting regularities on grammar-compressed strings
- Pal k is Linear Recognizable Online
- Repetition Detection in a Dynamic String
- 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
- Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
- 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
- Computing Longest Single-arm-gapped Palindromes in a String
- Palindromic Decompositions with Gaps and Errors
Cited In (9)
- Longest substring palindrome after edit
- Longest Lyndon Substring After Edit
- Shortest unique palindromic substring queries in semi-dynamic settings
- Minimal unique palindromic substrings after single-character substitution
- The heaviest induced ancestors problem: better data structures and applications
- Tight bound for the number of distinct palindromes in a tree
- Faster queries for longest substring palindrome after block edit
- Finding top-\(k\) longest palindromes in substrings
- Data structures for computing unique palindromes in static and non-static strings
Uses Software
Recommendations
- Computing Longest Common Substring and All Palindromes from Compressed Strings 👍 👎
- Efficient computation of longest single-arm-gapped palindromes in a string 👍 👎
- On finding a longest common palindromic subsequence 👍 👎
- Computing a Longest Common Palindromic Subsequence 👍 👎
- Counting Palindromes in Substrings 👍 👎
- Faster queries for longest substring palindrome after block edit 👍 👎
- Computing a Longest Common Palindromic Subsequence 👍 👎
- Longest substring palindrome after edit 👍 👎
- Computing Longest Single-arm-gapped Palindromes in a String 👍 👎
- Finding top-\(k\) longest palindromes in substrings 👍 👎
This page was built for publication: Computing longest palindromic substring after single-character or block-wise edits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227497)
