Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays (Q1177175)

The authors reconsider the Karp-Miller-Rosenberg (KMR) sequential algorithm for strings and pattern matching as a basic technique in parallel computation. The main result is a parallel version of the KMR algorithm computing the dictionary of basic factors of a string. Its complexity is \(O(\log(n)^ 2)\) time (\(n\) processors) on a CREW-PRAM model and \(O(\log n)\) (\(n\) processors) on a CRCW-PRAM model. This algorithm is used as a general framework for designing a large class of parallel algorithms for strings and arrays. Using the KMR parallel algorithm, the following problems are studied in the paper: 1. Searching for squares in strings. 2. Testing even palstars and compositions of \(k\)-palindromes (\(k=2,3,4\)) in a string. 3. Computing the maximal suffix and Lyndon factorization of a string. 4. Pattern matching in strings and arrays finding the longest repeated factor of a string, finding the maximal common factor of two strings, finding the longest symmetric factor of a string. The authors prove that all problems can be solved by parallel algorithms with the complexity of the KMR algorithm. Related to these problems, three open problems are presented at the end of the paper.