Longest Common Factor Made Fully Dynamic
Longest Common Factor Made Fully Dynamic
复制标题
最长公因数完全动态化
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Radoszewski
中科院分区：
文献类型：
--
作者：
A. Amir;P. Charalampopoulos;S. Pissis;J. Radoszewski
在最长的常见因素（LCF）问题中，我们得到了两个字符串$ s $和$ t $，最多最多$ n $，我们被要求找到$ s $和$ t的最长字符串$。这是计算机科学中的经典且研究的问题。即使更改单个字符，两个字符串的LCF长度也可能有很大差异。可以用$ \ tilde {\ Mathcal {o}}（n）$构建的数据结构（$ \ tilde {\ Mathcal {o}} $ notation $ notation抑制$ \ log^{\ Mathcal {\ Mathcal {O}（O}（O}（1）） } n $因素。迈向研究完全动态的LCF问题。在完全动态的版本中，在两个字符串中的任何一个中都允许编辑操作，并且在每个此类操作后，我们都将报告LCF。我们提出了第一个算法，该算法需要每个编辑操作都需要大量倾斜时间。特别是，我们展示了如何使用$ \ tilde {\ tilde {\ Mathcal {o}}}（n）$返回$ \ tilde {\ tilde {\ mathcal {o}}（n^{3/4}）$时间空间。我们还使用$ \ tilde {\ mathcal {o}}（\ sqrt {n}）$查询时间，在有限的情况下，仅在两个字符串之一中允许编辑和更快的几种动态限制变体的算法中的一个更快的算法，我们的查询时间很高和内部LCF问题（此处为“内部”意味着我们要回答有关特定文本多个因素的LCF的查询）。
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 $\tilde{\mathcal{O}}(n)$ (The $\tilde{\mathcal{O}}$ notation suppresses $\log^{\mathcal{O}(1)} n$ factors.) time and can return an LCF of the two strings after a single edit operation (that is reverted afterwards) in $\tilde{\mathcal{O}}(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 $\tilde{\mathcal{O}}(n^{3/4})$ time after each operation using $\tilde{\mathcal{O}}(n)$ space. We also present an algorithm with $\tilde{\mathcal{O}}(\sqrt{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).