The longest common extension problem revisited and applications to approximate string searching
The longest common extension problem revisited and applications to approximate string searching
复制标题
DOI：
10.1016/j.jda.2010.08.004
复制
发表时间：
2010-12-01
期刊：
影响因子：
--
通讯作者：
Tinta, Liviu
中科院分区：
文献类型：
--
作者：
Ilie, Lucian;Navarro, Gonzalo;Tinta, Liviu
最长公共扩展（Longest Common Extension，LCE）问题考虑一个字符串s，并为每对（i，j）计算s中从i和j开始的最长子串。它出现在许多基本字符串问题中，可以通过对字符串进行线性时间预处理来解决，该预处理允许（最坏情况下）对每对进行常数时间计算。这两种已知的方法使用强大的算法：要么是树中最低共同祖先的恒定时间计算，要么是数组中范围最小值的恒定时间计算。我们在这里表明，从实用的角度来看，这种复杂的方法是不需要的。我们给这个问题，不需要预处理两个非常简单的算法。第一种算法比以前最好的算法平均快5倍，而第二种算法几乎在所有输入上都更快。作为应用，我们修改的Landau-Vishkin算法的近似匹配使用我们最简单的LCE算法。所得到的算法是13到20倍的速度比原来的。我们比较它与更广泛使用的Ukkonen的截止算法，并表明它的行为更好的一个显着范围内的错误阈值。(C)2010年爱思唯尔B。V.保留所有权利。
The Longest Common Extension (LCE) problem considers a string s and computes, for each pair (i, j), the longest substring of s that starts at both i and j. It appears as a subproblem in many fundamental string problems and can be solved by linear-time preprocessing of the string that allows (worst-case) constant-time computation for each pair. The two known approaches use powerful algorithms: either constant-time computation of the Lowest Common Ancestor in trees or constant-time computation of Range Minimum Queries in arrays. We show here that, from practical point of view, such complicated approaches are not needed. We give two very simple algorithms for this problem that require no preprocessing. The first is 5 times faster than the best previous algorithms on the average whereas the second is faster on virtually all inputs. As an application, we modify the Landau-Vishkin algorithm for approximate matching to use our simplest LCE algorithm. The obtained algorithm is 13 to 20 times faster than the original. We compare it with the more widely used Ukkonen's cutoff algorithm and show that it behaves better for a significant range of error thresholds. (C) 2010 Elsevier B. V. All rights reserved.