A New Algorithm for Subset Matching Problem
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 ≤ 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).
DOI: https://doi.org/10.3844/jcssp.2007.924.933
Copyright: © 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.
- 3,078 Views
- 2,642 Downloads
- 2 Citations
Download
Keywords
- String matching
- tree pattern matching
- subset matching
- trie
- suffix tree
- probabilistic analysis