A New Algorithm for Subset Matching Problem
DOI : 10.3844/jcssp.2007.924.933
Journal of Computer Science
Volume 3, Issue 12
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 ≤ j≤ m). 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.