Research Article Open Access

A New Algorithm for Subset Matching Problem

Yangjun Chen1
  • 1 ,
Journal of Computer Science
Volume 3 No. 12, 2007, 924-933

DOI: https://doi.org/10.3844/jcssp.2007.924.933

Submitted On: 22 September 2007 Published On: 31 December 2007

How to Cite: Chen, Y. (2007). A New Algorithm for Subset Matching Problem. Journal of Computer Science, 3(12), 924-933. https://doi.org/10.3844/jcssp.2007.924.933

Abstract

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 position 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 ≤ jm). This is a generalization of the ordinary string matching and can be used for finding matching subtree patterns. In this research, we propose a new algorithm that needs O(n.m) time in the worst case. But its average time complexity is O(n + m.nlog1.5).

  • 999 Views
  • 1,602 Downloads
  • 1 Citations

Download

Keywords

  • String matching
  • tree pattern matching
  • subset matching
  • trie
  • suffix tree
  • probabilistic analysis