Tree Pattern Matching and Subset Matching in randomized O(nlog3 m) time

Richard Cole, Ramash Hariharan

Research output: Contribution to journalConference articlepeer-review

Abstract

The main goal of this paper is to give an efficient algorithm for the Tree Pattern Matching problem. We also introduce and give an efficient algorithm for the Subset Matching problem. The Subset Matching problem is to find all occurrences of a pattern string p of length m in a text string t of length n, where each pattern and text location is a set of characters drawn from some alphabet. The pattern is said to occur at text position i if the set p[j] is a subset of the set t[i+j-1], for all j, 1≤j≤m. We give an O((s+n)log2 m log(s+n)) randomized algorithm for this problem, where s denotes the sum of the sizes of all the sets. Then we reduce the Tree Pattern Matching problem to a number of instances of the Subset Matching problem. This reduction takes linear time and the sum of the sizes of the Subset Matching problems obtained is also linear. Coupled with our first result, this implies an O(n log2 m log n) time randomized algorithm for the Tree Pattern Matching problem.

Original languageEnglish (US)
Pages (from-to)66-75
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Tree Pattern Matching and Subset Matching in randomized O(nlog<sup>3</sup> m) time'. Together they form a unique fingerprint.

Cite this