A New Algorithm for Subset Matching Problem and Its Probabilistic Analysis

Y. Chen (Canada)


string matching, tree pattern matching, subset matching, trie, suffix tree, probabilistic analysis.


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 ordi nary string matching and can be used for finding matching subtree patterns. In this paper, we propose a new algorithm that needs only O(n + m) time in the case that the size of Σ is small and O(n + m⋅n0.5) time on average in general cases.

Important Links:

Go Back