Parallel Bi-dimensional Pattern Matching with Scaling

摘要

This paper deals with the problem of bi-dimensional pattern matching with scaling. The problem is to find all occurrences of the m x m pattern in the N x N text, scaled to all natural multiples. We have proposed an efficient parallel algorithm for this problem on CREW-PRAM with p~2 processors. It takes O(N~2/P~2) time.