The order-preserving pattern matching problem in practice


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

DISCRETE APPLIED MATHEMATICS, cilt.274, ss.11-25, 2020 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 274
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1016/j.dam.2018.10.023
  • Dergi Adı: DISCRETE APPLIED MATHEMATICS
  • Sayfa Sayıları: ss.11-25

Özet

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.