TY - GEN

T1 - Order preserving pattern matching on trees and DAGs

AU - Nakamura, Temma

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85030168258&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030168258&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-67428-5_23

DO - 10.1007/978-3-319-67428-5_23

M3 - Conference contribution

AN - SCOPUS:85030168258

SN - 9783319674278

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 271

EP - 277

BT - String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings

A2 - Venturini, Rossano

A2 - Fici, Gabriele

A2 - Sciortino, Marinella

PB - Springer Verlag

T2 - 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017

Y2 - 26 September 2017 through 29 September 2017

ER -