Approximate matching in the L∞ metric
Approximate matching in the L∞ metric
复制标题
DOI：
10.1016/j.ipl.2007.08.012
复制
发表时间：
2008-02-15
影响因子：
0.5
通讯作者：
Porat, Ely
中科院分区：
文献类型：
--
作者：
Lipsky, Ohad;Porat, Ely
设文本T =t（0），...，t（n-1）和模式P = p（0），...，p（m-1），自然数的字符串。在L-无限度量问题中的近似匹配中，对于每个文本位置i，输出是模式与从i开始的文本的长度m子串之间的L-无限距离，即，Max（j=0）（m-1）垂直条t（i+j）-p（j）垂直条。我们考虑近似k-L-无穷距离问题。如前所述，给定文本T和模式P，以及自然数k，问题的输出是仅在文本中的位置i处模式与文本的L无穷距离，其中距离由k限定。对于距离超过k的位置，输出为phi。我们展示了一个算法，解决了这个问题的O（n（k + log（min（m，vertical bar Sigma vertical bar）log m）时间。(c)2007 Elsevier B. V.保留所有权利。
Let a text T =t(0),..., t(n-1) and a pattern P = p(0),...,p(m-1), strings of natural numbers, be given. In the Approximate Matching in the L-infinity metric problem the output is, for every text location i, the L-infinity distance between the pattern and the length m substring of the text starting at i, i.e., Max(j=0)(m-1)vertical bar t(i+j) -p(j)vertical bar. We consider the Approximate k-L-infinity distance problem. Given text T and pattern P as before, and a natural number k the output of the problem is the L-infinity distance of the pattern from the text only at locations i in the text where the distance is bounded by k. For the locations where the distance exceeds k the output is phi. We show an algorithm that solves this problem in O(n(k + log(min(m, vertical bar Sigma vertical bar))) log m) time. (c) 2007 Elsevier B.V. All rights reserved.