Shape-preserving pattern matching

Two sequences of integers x and z of the same length m ≥ 2 are shape-isomorphic if, up to a positive proportional factor, the sequences of the distances between consecutive elements of x and z are the same, i.e., if for some ρ > 0 one has x[i + 1] − x[i] = ρ(z[i + 1] − z[i]), for each 1 ≤ i ≤ m − 1. In this paper we present two linear-time algorithms which, given a text y and a pattern x over an integer alphabet, finds all the factors of y that are shape-isomorphic to x. Our first solution is a two steps algorithm based on a reduction to the standard exact string matching problem, while our second solution is an online algorithm based on the well-known Knuth-Morris-Pratt string matching algorithm. We call this problem shape-preserving pattern-matching problem.