Efficient systolic string matching
Graham M. Megson · Electronics Letters · 1990
Two new string matching heuristics are presented which reduce the hardware requirement and improve the computation speed of the systolic string matcher due to Lipton and Lopresti1 The new array requires A = m/2 + n/2 −1 basic cells, T = m/2 + n/2 −1 + max (m, n) steps to match strings of size n and m,respectively, and has efficiency e = 1 (100%). A measure of the heuristic effectiveness compared with the minimum edit distance is also given