The order-preserving pattern matching problem in practice


Cantone D., Faro S., Külekci M. O.

DISCRETE APPLIED MATHEMATICS, vol.274, pp.11-25, 2020 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 274
  • Publication Date: 2020
  • Doi Number: 10.1016/j.dam.2018.10.023
  • Title of Journal : DISCRETE APPLIED MATHEMATICS
  • Page Numbers: pp.11-25

Abstract

Given a pattern x of length m and a text y of length n, both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few.