Longest property-preserved common factor: a new string-processing framework

DOI10.1016/j.tcs.2020.02.012zbMath1435.68395arXiv1810.02099OpenAlexW3006214012MaRDI QIDQ2297866

Giulia Bernardini, Lorraine A. K. Ayad, Nadia Pisanti, Costas S. Iliopoulos, Solon P. Pissis, Giovanna Rosone, Roberto Grossi

Publication date: 20 February 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

palindromic factorsperiodic factorssquare-free factors

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Longest common rollercoasters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient seed computation revisited
• Linear-time computation of local periods
• Suffix tree characterization of maximal motifs in biological sequences
• Lossless filter for multiple repetitions with Hamming distance
• Sublinear approximate string matching and biological applications
• On finding a longest common palindromic subsequence
• Property suffix array with applications
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Sublinear Space Algorithms for the Longest Common Substring Problem
• On Prefix/Suffix-Square Free Words
• Algorithms on Strings, Trees and Sequences
• Time-Space Trade-Offs for the Longest Common Substring Problem
• A Linear-Time Algorithm for Seeds Computation
• Longest common substring made fully dynamic
• Longest substring palindrome after edit
• Linear-Time Algorithm for Long LCF with k Mismatches
• The “Runs” Theorem
• Computing a Longest Common Palindromic Subsequence
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Longest common prefixes with \(k\)-errors and applications
• Longest property-preserved common factor