...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Linear-Time Algorithm for Long LCF with k Mismatches
【24h】

Linear-Time Algorithm for Long LCF with k Mismatches

机译：具有k个不匹配的长LCF的线性时间算法

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the Longest Common Factor with k Mismatches (LCF_k) problem, we are given two strings X and Y of total length n, and we are asked to find a pair of maximal-length factors, one of X and the other of Y, such that their Hamming distance is at most k. Thankachan et al. [Thankachan et al. 2016] show that this problem can be solved in O(n log^k n) time and O(n) space for constant k. We consider the LCF_k(l) problem in which we assume that the sought factors have length at least l. We use difference covers to reduce the LCF_k(l) problem with l=Omega(log^{2k+2}n) to a task involving m=O(n/log^{k+1}n) synchronized factors. The latter can be solved in O(m log^{k+1}m) time, which results in a linear-time algorithm for LCF_k(l) with l=Omega(log^{2k+2}n). In general, our solution to the LCF_k(l) problem for arbitrary l takes O(n + n log^{k+1} n/sqrt{l}) time.
机译：在具有k个不匹配项的最长公共因子（LCF_k）问题中，我们给了两个字符串X和Y，它们的总长度为n，并要求我们找到一对最大长度因子，其中一个X和另一个Y，例如他们的汉明距离最多为k。 Thankachan等。 [Thankachan等。 2016]表明，这个问题可以在O（n log ^ k n）时间和常数为k的O（n）空间中解决。我们考虑LCF_k（l）问题，在该问题中，我们假设寻找的因子的长度至少为1。我们使用差异覆盖来将l = Omega（log ^ {2k + 2} n）的LCF_k（l）问题减少到涉及m = O（n / log ^ {k + 1} n）个同步因子的任务。后者可以在O（m log ^ {k + 1} m）的时间内求解，这导致LCF_k（l）的线性时间算法为l = Omega（log ^ {2k + 2} n）。通常，对于任意l的LCF_k（l）问题，我们的解决方案花费O（n + n log ^ {k + 1} n / sqrt {l}）时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号