For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Simple Heuristic for Order-Preserving Matching
Joong Chae NA Inbok LEE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2019/03/01
Online ISSN: 1745-1361
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.