Abstract
Let T = t1 t2 …… tn and P = p1 p2 …… pm be two strings. The pattern P matches T at position i if P is equal to the substring ti ti+1 ... ti+m–1. For any real number k 3 1, let k × P denote the string obtained by proportionally enlarging P by a scale of k. We say that P real scaled matches T at position i if there exists a real scale k 3 1 such that k × P matches T at position i. Moreover, we say that there is a real scaled occurrence of P in T at position I if P real scaled matches T at position i. The problem of real scaled matching refers to the finding of all real scaled occurrences of P in T. Real scaled matching is an important problem originally inspired by problems in the field of computer vision. Previously, Amir et al. efficiently solved it in O(m + n) time and asked the following open problem: “Can we efficiently preprocess T in a manner that will enable, upon inputting a pattern P, finding all real scaled occurrences of P in T in O(m + tocc) time, where tocc is the number of real scaled occurrences of P in T?” Such a problem is called the on-line real scaled matching. In this thesis, we study the on-line real scaled matching problem. Intuitively, since the scale k can be any real number 3 1, it seems that there may be exponential patterns that can real scaled match T and thus impossible to have a polynomial-time preprocessing algorithm. Fortunately, in this thesis, we firstly derive a novel property from which we can conclude that there are at most O(n3) patterns that can real scaled match a given text T. Then, we give an O(n5)-time algorithm to preprocess T such that the finding of all real scaled occurrences of any pattern P can be done in O(m + tocc) time. Our result is the first solution to Amir et al.’s open problem.