Longest Common Factor Made Fully Dynamic
share
In the longest common factor (LCF) 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 in both S and T. This is a classical and well-studied problem in computer science. The LCF length for two strings can vary greatly even when a single character is changed. A data structure that can be built in Õ(n) (The Õ notation suppresses ^O(1) n factors.) time and can return an LCF of the two strings after a single edit operation (that is reverted afterwards) in Õ(1) time was very recently proposed as a first step towards the study of the fully dynamic LCF problem. In the fully dynamic version, edit operations are allowed in any of the two strings, and we are to report an LCF after each such operation. We present the first algorithm that requires strongly sublinear time per edit operation. In particular, we show how to return an LCF in Õ(n^3/4) time after each operation using Õ(n) space. We also present an algorithm with Õ(√(n)) query time for the restricted case where edits are allowed only in one of the two strings and faster algorithms for several restricted variants of dynamic and internal LCF problems (here `internal' means that we are to answer queries about LCF on multiple factors of a given text).
READ FULL TEXT