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
