Real Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Real scaled matching is an important problem that was originally inspired by Computer Vision. In this paper, we present a new, more precise and realistic, definition for one dimensional real scaled matching, and an efficient algorithm for solving this problem. For a text of length n and a pattern of length m, the algorithm runs in time O(n log m + n~(1/2)m~(3/2) (log m)~(1/2)).
展开▼
机译:实际比例匹配是指找到文本中出现的所有位置的问题,该位置根据任意实际尺寸比例按比例放大。实际比例匹配是一个重要的问题,最初是由Computer Vision启发的。在本文中,我们为一维实数比例匹配提出了一种新的,更精确和现实的定义,以及一种解决该问题的有效算法。对于长度为n的文本和长度为m的模式,该算法在时间O(n log m + n〜(1/2)m〜(3/2)(log m)〜(1/2))中运行。
展开▼