Efficient CRCW-PRAM algorithms for universal substring searching (Q1208721)

The author develops a standard representation for strings supporting string queries in constant time. It is shown that if all strings \(W\) are given in their individual standard representations, then a CRCW-PRAM with \(O(\{\overline n\}=\sum_{h=1}^{t}\mid \overline{w}_ h\mid+\mid w'\mid)\) processors can find all the occurrences of any \(w'\) in any set \(W'=\{\overline{w}_ 1,\overline{w}_ 2,\dots, \overline{w}_ t\}\) from \(W\), in constant time. Putting a string \(x\) in such a standard representation requires \(O(\log\mid x\mid)\) CRCW-PRAM steps and \(O(\mid x\mid\log \mid x\mid)\) total work and space. Thus, in particular, searching for any substring of a pattern of size \(m\) in any substring of a text of size \(n\) can be done in constant time with at most \(n+m\) processors, once both the text and pattern have been put in standard form at a cost of \(O((n+m)\log n)\) operations. Basically this approach consists of precomputing some ``universal'' substrings in the textstring, which are used to latch on possible occurrences of any individual pattern. These substrings are universal in the sense that they reflect structural properties of the text, independently of any particular pattern. Reversing the usual perspective of string searching, this method searches for occurrences of such text substrings into any given pattern, and a careful organization of the latter represents the way in which the total work is reduced.