Longest common factor after one edit operation

DOI10.1007/978-3-319-67428-5_2MaRDI QIDQ5150915zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Jakub Radoszewski

Publication date 16 February 2021

Published in String Processing and Information Retrieval (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-67428-5_2

zbMATH Keywords

dynamic data structureheavy-path decompositionlongest common factororthogonal range searchingsuffix tree

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Locally maximal common factors as a tool for efficient dynamic string algorithms
• A fast longest common subsequence algorithm for similar strings
• Dynamic and internal longest common substring
• Computing longest palindromic substring after single-character or block-wise edits
• Longest substring palindrome after edit

Cites work

• A note on the longest common substring with k-mismatches problem
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Computing the longest common substring with one mismatch
• Dynamic text and static pattern matching
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Longest common substring with approximately \(k\) mismatches
• Longest common substrings with k mismatches
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Sublinear space algorithms for the longest common substring problem
• Time-space trade-offs for the longest common substring problem

Cited in

(17)

• 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
• Dynamic and internal longest common substring
• Computing longest palindromic substring after single-character or block-wise edits
• Repetition Detection in a Dynamic String
• Longest common substring made fully dynamic
• Faster queries for longest substring palindrome after block edit
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Longest substring palindrome after edit
• Longest Lyndon Substring After Edit
• The heaviest induced ancestors problem revisited
• scientific article; zbMATH DE number 7765421 (Why is no real title available?)
• Data structures for computing unique palindromes in static and non-static strings
• Dynamic longest common substring in polylogarithmic time
• A textbook solution for dynamic strings
• Shortest cover after edit

This page was built for publication: Longest common factor after one edit operation

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