Efficient parallel hardware algorithms for string matching

This paper presents efficient parallel hardware algorithms for string match ing. Two subproblems known as the exact matching and the k-mismatches probl ems are covered. Systolic array architectures are developed using dataflow algorithms. Forwarding and broadcasting mechanisms provide high-performance parallel solutions to these problems. Time complexities of these parallel algorithms are O((n/d + alpha), 0 less than or equal to alpha less than or equal to m, where n and m represent lengths of reference and pattern string s (n much greater than m) and d represents the degree of parallelism. The d egree of parallelism is controllable by using a variable number (d) of inpu t land output) streams. Special purpose VLSI chip design schemes are presen ted with a hierarchical and linear systolic array of cells. With the linear systolic array architecture, m identical PEs are needed for a serial desig n and d * m identical PEs are needed for a parallel design. (C) 1999 Elsevi er Science B.V. All rights reserved.