B. Pradeep et Csr. Murthy, A CONSTANT-TIME STRING SHUFFLE ALGORITHM ON RECONFIGURABLE MESHES, International journal of computer mathematics, 68(3-4), 1998, pp. 251-259
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.