A multipattern matching algorithm using sampling and bit index
Jinhui Chen, Zhongfu Ye, Min Tang · 2008
Pattern matching is one of the basic problems in computer science. In this paper we propose a new multiple pattern matching algorithm. Unlike the well known Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin and their variants, our algorithm is derived from the ideas of sampling and bit index, sampling for efficiency and bit index for flexibility, as a result providing the simplest way to search for multiple patterns. Theoretical analysis and experimental results show that our algorithm is average-optimal with average complexity of O(n/m) for the search of patterns of length m in a text of length n. It provides a proper solution to such needs as matching long dispersed patterns and especially bit pattern matching (newly introduced in this paper) in data analysis of some private protocols' communication.