In the longest common substring (LCS) problem, we are given two strings S and T , each of length at most n, and we are asked to find a longest string occurring as a fragment of both S and T . This is a classical and well-studied problem in computer science with a known O(n)-time solution. In the fully dynamic version of the problem, edit operations are allowed in either of the two strings, and we are asked to report an LCS after each such operation. We present the first solution to this problem that requires sublinear time per edit operation. In particular, we show how to return an LCS inÕ(n 2/3 ) 1 time (orÕ( √ n) time if edits are allowed in only one of the two strings) after each operation usingÕ(n) space. This line of research was recently initiated by the authors [SPIRE 2017] in a somewhat restricted dynamic variant. AnÕ(n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) inÕ(1) time was presented. At CPM 2018, three papers studied analogously restricted dynamic variants of problems on strings. We show that our techniques can be used to obtain fully dynamic algorithms for several classical problems on strings, namely, computing the longest repeat, the longest palindrome and the longest Lyndon substring of a string. The only previously known sublinear-time dynamic algorithms for problems on strings were obtained for maintaining a dynamic collection of strings for comparison queries and for pattern matching with the most recent advances made by Gawrychowski et al. [SODA 2018] and by Clifford et al. [STACS 2018]. As an intermediate problem we consider computing the required result on a string with a given set of k edits, which leads us, in particular, to answering internal queries on a string. The input to such a query is specified by a substring (or substrings) of a given string. Data structures for answering internal queries that were proposed by Kociumaka et al. [SODA 2015] and by Gagie et al. [CCCG 2013] are used, along with new data structures for several types of queries that we develop -these queries include computing an LCS on multiple substrings. However, as it is likely that the most general internal LCS queries cannot be answered efficiently, we also design a different scheme that requires an application of difference covers. Other ingredients of our algorithms include the suffix tree, heavy-path decompositions, orthogonal range queries, and string periodicity.
Subsequently, Amir et al. REF considered a fully dynamic version of the problem, in which the edit operations are applied sequentially.
Longest Common Substring Made Fully Dynamic
arXiv: Data Structures and Algorithms
Mathematics Computer Science