Journal of Computer Science

A New Algorithm for Subset Matching Problem

Yangjun Chen

DOI : 10.3844/jcssp.2007.924.933

Journal of Computer Science

Volume 3, Issue 12

Pages 924-933


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


© 2007 Yangjun Chen. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.