A Simple Heuristic for Order-Preserving Matching

Joong Chae NA  Inbok LEE  

IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.502-504
Publication Date: 2019/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018FCL0004
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
string algorithm,  range minimum query,  order preserving matching,  

Full Text: PDF(184.2KB)
>>Buy this Article

Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.