Longest Common Substring Made Fully Dynamic
Longest Common Substring Made Fully Dynamic
复制标题
最长公共子串完全动态化
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Radoszewski
中科院分区：
文献类型：
--
作者：
A. Amir;P. Charalampopoulos;S. Pissis;J. Radoszewski
在最长公共子串（LCS）问题中，我们有两个字符串$S$和$T$，每个字符串的长度都不超过$n$，我们被要求找到一个作为$S$和$T$的片段出现的最长字符串。这是计算机科学中一个经典且研究得很充分的问题，具有已知的$mathcal{O}(n)$时间解。在该问题的完全动态版本中，允许对两个字符串中的任何一个进行编辑操作，并且要求我们在每次这样的操作之后报告LCS。我们提出了这个问题的第一个解决方案，它需要每次编辑操作的次线性时间。特别地，我们将展示如何在每次操作后使用$ ilde{mathcal{O}}(n^{2/3})$ time(或$ ilde{mathcal{O}}(sqrt{n})$ time（如果只允许对两个字符串中的一个进行编辑）$ ilde{mathcal}}(n)$ space返回LCS。
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 $mathcal{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 $ ilde{mathcal{O}}(n^{2/3})$ time (or $ ilde{mathcal{O}}(sqrt{n})$ time if edits are allowed in only one of the two strings) after each operation using $ ilde{mathcal{O}}(n)$ space.
This line of research was recently initiated by the authors [SPIRE 2017] in a somewhat restricted dynamic variant. An $ ilde{mathcal{O}}(n)$-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in $ ilde{mathcal{O}}(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].
重温最重的诱发祖先问题
DOI：
10.4230/lipics.cpm.2018.20
发表时间：
2018
期刊：
{CPM} 2018
影响因子：
--
作者：
Abedin, P.;Hooshmand, S.;Ganguly, A.;Thankachan, S.V.
通讯作者：
Thankachan, S.V.