Name
Abstract | ||
|---|---|---|
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 + m log 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-73117-9_44 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Order-preserving pattern matching,Duel-and-sweep | Conference | 10706 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Davaajav Jargalsaikhan | 1 | 0 | 0.34 |
| Diptarama | 2 | 0 | 2.03 |
| Ryo Yoshinaka | 3 | 172 | 26.19 |
| Ayumi Shinohara | 4 | 936 | 88.28 |