A FAST PATTERN-MATCHING ALGORITHM ON MODULAR MESH-CONNECTED COMPUTERS WITH MULTIPLE BUSES

摘要

Given a pattern of length m and a text of length n, commonly m < < n, this paper presents a randomized parallel algorithm for pattern matching in O(n~(1/10)) (=O(n~(1/10) + (n — m)~(1/10))) time on a newly proposed n~(3/5) x n~(2/5) modular mesh-connected computers with multiple buses. Furthermore, the time bound of our parallel algorithm can be reduced to O(n~(1/11)) if fewer processors are used.