A fast algorithm for order-preserving pattern matching

作者：Cho Sukhyeun; Na Joong Chae; Park Kunsoo; Sim Jeong Seop^*

来源：Information Processing Letters, 2015, 115(2): 397-402.

DOI：10.1016/j.ipl.2014.10.018

• Analysis of algorithms
• Order-preserving pattern matching
• Order-isomorphism
• Horspool algorithm
• KMP algorithm

Given a text T and a pattern P, the order-preserving pattern matching (OPPM) problem is to find all substrings in T which have the same relative orders as P. The OPPM has been studied in the fields of finding some patterns affected by relative orders, not by their absolute values. In this paper, we present a method of deciding the order-isomorphism between two strings even when there are same characters. Then, we show that the bad character rule of the Horspool algorithm for generic pattern matching problems can be applied to the OPPM problem and we present a space-efficient algorithm for computing shift tables for text search. Finally, we combine our bad character rule with the KMP-based algorithm to improve the worst-case running time. We give experimental results to show that our algorithm is about 2 to 6 times faster than the KMP-based algorithm in reasonable cases.

• 出版日期2015-2