FAST ALGORITHMS FOR APPROXIMATELY COUNTING MISMATCHES
FAST ALGORITHMS FOR APPROXIMATELY COUNTING MISMATCHES
复制标题
DOI：
10.1016/0020-0190(93)90177-b
复制
发表时间：
1993-11-08
影响因子：
0.5
通讯作者：
KARLOFF, H
中科院分区：
文献类型：
--
作者：
KARLOFF, H
给定一个文本字符串\(T\in\sum_{}^{n}\)以及一个模式字符串\(P\in\sum_{}^{m}\)，对于每个\(i = 1,2,\cdots,n - m + 1\)，定义\(f(i)\)为当模式在文本下方对齐且从文本的第\(i\)个位置开始时不匹配的数量。当字母表是任意的时候，计算所有\(f(i)\)的已知最快算法在最坏情况下的时间超过\(n\sqrt{m}\)。对于任意\(\epsilon>0\)，我们给出简单的随机化算法和确定性算法来计算\(g(i)\)，使得对于所有\(i\)都有\(f(i)\leq g(i)\leq f(i)(1 + \epsilon)\)。这些算法的运行时间为\(O((\frac{n}{\epsilon^{2}})\log_{c}m)\)，其中\(c\)是一个小的通用常数，并且从任意\(\sum\)的情况到\(\sum = \{0,1\}\)的情况很容易归约。
Given a text string T is-an-element-of SIGMA(n) and a pattern string P is-an-element-of SIGMA(m), for each i = 1, 2,...,n-m + 1 define f(i) to be the number of mismatches when the pattern is aligned below the text and starts in position i of the text. The fastest known algorithm to compute all the f(i)'s when the alphabet is arbitrary has worst-case time exceeding n square-root m.For any epsilon > 0, we give simple randomized and deterministic algorithms that compute g(i) such that f(i) less-than-or-equal-to g(i) less-than-or-equal-to f(i)(1 + epsilon) for all i. The algorithms run in time O((n/epsilon2) log(c)m) for a small universal constant c and are easy reductions from the case of arbitrary SIGMA to the case of SIGMA = (0, 1}.