Faster Algorithms for Longest Common Substring

doi:10.1145/3774754

Faster Algorithms for Longest Common Substring

2026-04-01

0

PRE

AI

DOI：10.1145/3774754

原文求助

摘要

En 中文

在经典的“最长公共子串”（LCS）问题中，我们给定两个总长度为n的字符串S和T，它们基于一个大小为sigma的字母表，并要求找出同时作为S和T的片段出现的最长字符串。Weiner在其引入后缀树的奠基性论文中，提出了一个时间复杂度为O(n log sigma)的LCS算法[SWAT 1973]。对于多项式有界的整数字母表，Farach的线性时间后缀树构造方法给出了一个时间复杂度为O(n)的LCS算法[FOCS 1997]。然而，对于小字母表，在计算模型的字RAM模型中，这并非LCS问题的最优解，在该模型中，字符串可以存储在O(n log sigma/log n)的空间中，并以O(n log Q/log n)的时间读取。我们证明了在字RAM模型中，可以在时间O(n log sigma/ log n)内计算两个字符串的LCS，当sigma = 2(omicron)((根号log n))（特别是当sigma = O(1)）时，该时间复杂度是亚线性的，并使用最优空间O(n log sigma/ log n)。实际上，最近的研究表明这一结果是条件最优的[Kempa and Kociumaka, STOC 2025]。对于计算lambda = O(根号(log n/log log n))个总长度为n的输入字符串的LCS，也可以达到相同的复杂度。然后我们将这些思想推广到计算k-不匹配LCS的问题，该问题近年来受到了广泛关注。在此问题中，目标是计算S的最长子串，该子串在T中出现时最多有k个不匹配。Flouri等人展示了如何以O(n log n)的时间计算1-不匹配LCS[IPL 2015]。Thankachan等人将这一结果扩展到k-不匹配LCS的计算，对于k = O(1)，时间复杂度为O(n log(k) n)[J. Comput. Biol. 2016]。我们提出了一种时间复杂度为O(n log(k-0.5) n)的算法，适用于任何常数整数k > 0，且与字母表大小无关，使用的空间为O(n)，与之前的方法相同。因此，我们显著突破了著名的n logk n屏障，该屏障源于Cole等人首次在字符串索引中引入k误差的递归重路径分解技术[STOC 2004]。作为副产品，我们改进了Charalampopoulos等人[CMP 2018]关于计算k-不匹配LCS的算法，特别是在输出k-不匹配LCS足够长的情况下。

Keyword:

longest common substring

k mismatches

wavelet tree

Faster Algorithms for Longest Common Substring

摘要

期刊

机构

引用论文