Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431147 | Journal of Discrete Algorithms | 2007 | 7 Pages |
Abstract
Real Scaled Matching is 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(nlogm+nm3/2logm).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Dekel Tsur,