Name
Abstract | ||
|---|---|---|
The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m+N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-67428-5_23 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Conference | 10508 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tenma Nakamura | 1 | 0 | 0.34 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Masayuki Takeda | 4 | 902 | 79.24 |