Dynamic and Internal Longest Common Substring

Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis*, Jakub Radoszewski

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n) -time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to the fully dynamic LCS problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in O~ (n2 / 3) time, after O~ (n) -time and space preprocessing. This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, the authors presented an O~ (n) -sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in O~ (1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings; specifically, computing the longest palindrome and the Lyndon factorization of a string after a single edit operation. We develop dynamic sublinear-time algorithms for both of these problems as well. We also consider internal LCS queries, that is, queries in which we are to return an LCS of a pair of substrings of S and T. We show that answering such queries is hard in general and propose efficient data structures for several restricted cases.

Original languageEnglish
Pages (from-to)3707-3743
Number of pages37
JournalAlgorithmica
Volume82
Issue number12
Early online date15 Jul 2020
DOIs
Publication statusPublished - 1 Dec 2020

Keywords

  • Dynamic algorithms
  • Longest common substring
  • String algorithms

Fingerprint

Dive into the research topics of 'Dynamic and Internal Longest Common Substring'. Together they form a unique fingerprint.

Cite this