.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
摘要给定两个字符串 S 和 T，长度均不超过 n，最长公共子串（LCS）问题是寻找 S 和 T 共有的最长子串。这是计算机科学中的一个经典问题，存在一个 $$\mathcal {O}(n)$$
O
(
n
)
时间复杂度的解决方案。在完全动态设置下，允许对两个字符串中的任意一个进行编辑操作，问题是在每次编辑后寻找LCS。我们提出了首个完全动态LCS问题的解决方案，其每次编辑操作的时间复杂度为 n 的次线性时间。具体来说，我们展示了如何在经过 $$\tilde{\mathcal {O}}(n^{2/3})$$
O
~
(
n
2
/
3
)
时间后，每次编辑操作后寻找LCS，且经过了 $$\tilde{\mathcal {O}}(n)$$
O
~
(
n
)
时间和空间的预处理。这一研究方向最近由Amir等人 [SPIRE 2017] 在一个受限的动态变体中首次提出。更具体地说，作者提出了一种大小为 $$\tilde{\mathcal {O}}(n)$$
O
~
(
n
)
的数据结构，在单次编辑操作（随后撤销）后返回两个字符串的LCS，时间复杂度为 $$\tilde{\mathcal {O}}(1)$$
O
~
(
1
)
。在CPM 2018上，三篇论文（Abedin等人、Funakoshi等人、Urabe等人）研究了字符串问题的类似受限动态变体；具体来说，在单次编辑操作后计算字符串的最长回文和Lyndon分解。我们也为这两个问题开发了动态次线性时间算法。我们还考虑了内部LCS查询，即返回 S 和 T 的子串对的LCS的查询。我们表明，在一般情况下回答此类查询是困难的，并针对几种受限情况提出了高效的数据结构。
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息