@article{MAE3AA718,
title = "Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching",
journal = "Journal of KIISE, JOK",
year = "2018",
issn = "2383-630X",
doi = "10.5626/JOK.2018.45.8.778",
author = "Youkun Shin,Youngho Kim,Jeong Seop Sim",
keywords = "order-preserving pattern matching,order-preserving multiple pattern matching,Z-function,parallel algorithm",
abstract = "Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T which are order-isomorphic to P. Given a text T of length n and a set of patterns W={P₁, P₂,…, P<SUB>b</SUB>}, the order-preserving multiple pattern matching problem is to find all substrings in T which are order-isomorphic to patterns of W. In this paper, we present two parallel algorithms based on the Z-function. The first algorithm for the order-preserving pattern matching problem runs in O(m) time using O(n+hm) threads and the second algorithm for the order-preserving multiple pattern matching problem runs in O(n+M) time using O(b(n+M)) threads, where h is the number of blocks and M is the length of the longest pattern in W. Experimental results show that our parallel algorithm for the order-preserving pattern matching problem is approximately 71.2 times faster than the sequential algorithm when m=10 and n=1,000,000, and that our parallel algorithm for the order-preserving multiple pattern matching problem is approximately 12.2 times faster than the sequential algorithm when b=1,000, m=10, and n=1,000."
}