We revisit the problem of indexing a string S[1..n] to support searching all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m~k) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m+occ+log n log log n) time. The previously best solution achieving this time complexity requires an index of size O(n log n). This new index can be used to improve existing indexes for k ≥ 2 errors. Among others, it can support matching with k = 2 errors in O(m log n log log n + occ) time.
展开▼
机译：我们将重新讨论索引字符串S [1..n]的问题，以支持搜索S中与给定模式P [1..m]匹配的所有子字符串，且最多有k个错误。先前的解决方案要么需要以k为单位的大小指数索引，要么需要Ω（m〜k）时间进行搜索。受DNA序列索引的驱动，我们研究了仅占用O（n）空间的空间高效索引。对于k = 1，我们给出一个索引来支持O（m + occ + log n log log n）时间的匹配。实现此时间复杂度的先前最佳解决方案需要大小为O（n log n）的索引。此新索引可用于改进k≥2个错误的现有索引。其中，它可以支持O（m log n log log n + occ）时间中k = 2个错误的匹配。
展开▼
