TY - GEN
T1 - Duel and sweep algorithm for order-preserving pattern matching
AU - Jargalsaikhan, Davaajav
AU - Diptarama,
AU - Ueki, Yohei
AU - Yoshinaka, Ryo
AU - Shinohara, Ayumi
N1 - Funding Information:
Acknowledgements. This work is supported by Tohoku University Division for Interdisciplinary Advance Research and Education, ImPACT Program of Council for Science, Technology and Innovation (Cabinet Office, Government of Japan), and JSPS KAKENHI Grant Number JP15H05706.
Publisher Copyright:
© 2018, Springer International Publishing AG.
PY - 2018
Y1 - 2018
N2 - Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of the pattern in the text. Unlike exact matching, order-preserving pattern matching (OPPM) considers the relative order of elements, rather t han their real values. In this paper, we propose an efficient algorithm for the OPPM problem using the “duel-and-sweep” paradigm. For a pattern of length m and a text of length n, our algorithm runs in O(n+ mlog m) time in general, and in O(n+ m) time under an assumption that the characters in a string can be sorted in linear time with respect to the string size. We also perform experiments and show that our algorithm is faster than the KMP-based algorithm.
AB - Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of the pattern in the text. Unlike exact matching, order-preserving pattern matching (OPPM) considers the relative order of elements, rather t han their real values. In this paper, we propose an efficient algorithm for the OPPM problem using the “duel-and-sweep” paradigm. For a pattern of length m and a text of length n, our algorithm runs in O(n+ mlog m) time in general, and in O(n+ m) time under an assumption that the characters in a string can be sorted in linear time with respect to the string size. We also perform experiments and show that our algorithm is faster than the KMP-based algorithm.
KW - Duel-and-sweep
KW - Order-preserving pattern matching
UR - http://www.scopus.com/inward/record.url?scp=85041847550&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041847550&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-73117-9_44
DO - 10.1007/978-3-319-73117-9_44
M3 - Conference contribution
AN - SCOPUS:85041847550
SN - 9783319731162
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 624
EP - 635
BT - SOFSEM 2018
A2 - Wiedermann, Jirí
A2 - Tjoa, A Min
A2 - Biffl, Stefan
A2 - Bellatreche, Ladjel
A2 - van Leeuwen, Jan
PB - Springer Verlag
T2 - 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Y2 - 29 January 2018 through 2 February 2018
ER -