A CONSTANT-TIME STRING SHUFFLE ALGORITHM ON RECONFIGURABLE MESHES

The string shuffle problem is to verify whether a string, S, of length n can be constructed by arbitrarily interleaving the characters of tw o other strings of lengths m and n-m (0 < m < n) such that the origina l order of the characters in these two strings is maintained in S. In this paper, we present an O(1) time algorithm for the string shuffle p roblem on an nxn processor array with reconfigurable bus system (recon figurable mesh). The previous best parallel algorithm for the string s huffle problem takes O(log(2)n) time using O(n(2)/log(2)n) processors. Our algorithm is simpler and adopts an entirely different approach wh en compared to the earlier algorithms.