15.1 INTRODUCTION
String matching is employed in several applications, such as packet classification, computational biology, spam blocking, and information retrieval. String search operates on a given alphabet set Σ of size |Σ|, a pattern P = p0p1 … pm−1 of length m, and a text string T = t0t1 … tn−1 of length n, with m ≤ n. The problem is to find all occurrences of the pattern P in the text string T. The average time complexity for implementing the string search problem on a single processor was proven to be O(n) [99]. We refer the reader to Reference 100 for a comprehensive review of the different hardware implementations of the string matching problem.
A hardware implementation for the search engine can be assumed to have the following characteristics:
18.118.144.12