Efficient CRCW-PRAM Algorithms Combining Multiple Autonomous Databases
Alberto Apostolico · Purdue e-Pubs (Purdue University System) · 1991
A standard representation for strings is proposed, which has the following properties.(1) For any string x, putting x in such a standard representation requires O(log Ixl) CRCW-PRAM steps and O(lxllog Ixl) total work and space.(2) Let W be a collection of strings individually given in stich a standard representation.Let w be an arbitrarily chosen string in W, w' an arbitrary substring ofw, and {WI,W2, ... ,Wt} an arbitrary set of substrings of strings in W.Then, a CRCW PRAM with O(n = L~=I IWh! + Iw'l) processors will find all the occurrences of w' in {WI, W2, ... , wtl, in constant time.