This article presents a real-time randomized streaming string-matching algorithm that uses O (log m ) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurrences of the pattern, but never missing an actual occurrence.

In the packed string matching problem, each machine word accomodates alpha characters, thus an n-character text occupies n/alpha memory words. We extend the Crochemore-Perrin constant-space O(n)-time string matching algorithm to run in optimal O(n/alpha) time and even in real-time, achieving a factor alpha speedup over traditional algorithms that examine each character individually. Our solution can be efficiently implemented, unlike prior theoretical packed string matching work. We adapt the standard RAM model and only use its AC0 instructions (i.e. no multiplication) plus two specialized AC0 packed string instructions. The main string-matching instruction is available in commodity processors (i.e. Intel's SSE4.2 and AVX Advanced String Operations); the other maximal-suffix instruction is only required during pattern preprocessing. In the absence of these two specialized instructions, we propose theoretically-efficient emulation using integer multiplication (not AC0) and table lookup.

An optimal $O(\log \log n)$-time concurrent-read concurrent-write parallel algorithm for detecting all squares in a string is presented. A tight lower bound shows that over general alphabets, this is the fastest possible optimal algorithm. When p processors are available, the bounds become $\Theta \lceil {({{n\log n)} p}\rceil + \log \log _{\lceil {1 + {p / n}} \rceil } 2p} )$. The algorithm uses an optimal parallel string-matching algorithm together with periodicity properties to locate the squares within the input string.

This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An O(log n) time, n-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only nlog n processors, and thus achieves an optimalspeedup. 2. An O(log log n) time, n log nloglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.

A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself, and quasiperiodic if it is covered by some shorter string. We present an on-line linear-time algorithm that tests if each prefix of an input string is superprimitive while the string is given a symbol at a time.

This paper presents an $\Omega (\log \log m)$ lower bound on the number of rounds necessary for finding occurrences of a pattern string $P[1..m]$ in a text string $T[1..2m]$ in parallel using m comparisons in each round. The bound is within a constant factor of the fastest algorithm for this problem [D. Breslauer and Z. Galil, SIAM J. Comput.,19 (1990), pp. 1051–1058] and also holds for an m-processor CRCW-PRAM in the case of a general alphabet. Consequently, the paper derives the parallel complexity of the string matching problem using p processors for general alphabets, which is • $\Theta ( \frac{m}{p} )$ if $p \leq \frac{m}{{\log \log m}}$, • $\Theta (\log \log m)$ if $\frac{m}{{\log \log m}} \leq p \leq m$, • $\Theta (\log \log _{2p/m} p)$ if $m \leq p \leq m^2 $, • $\Theta (1)$ if $p \geq m^2 $, or in short $\Theta \lceil \frac{m}{p} \rceil + \log \log _{\lceil 1 + p/m \rceil } 2p)$.

This talk presents the derivation of an\\Omega\\Gamma/28 log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P [1::m] in a text string T [1::2m] in parallel using m comparisons in each round. The parallel complexity of the string matching problem using p processors for general alphabets follows. 1. Introduction Better and better parallel algorithms have been designed for string-matching. All are on CRCW-PRAM with the weakest form of simultaneous write conflict resolution: all processors which write into the same memory location must write the same value of 1. The best CREW-PRAM algorithms are those obtained from the CRCW algorithms for a logarithmic loss of efficiency. Optimal algorithms have been designed: O(logm) time in [8, 17] and O(log log m) time in [4]. (An optimal algorithm is one with pt = O(n) where t is the time and p is the number of processors used.) Recently, Vishkin [18] developed an optimal O(log m) time algorithm. Unlike...

An optimal $O(\log \log n)$ time parallel algorithm for string matching on CROW-PRAM is presented. It improves previous results of Galil [Inform, and Control, 67 (1985), pp. 144–157] and Vishkin [Inform, and Control, 67 (1985), pp. 91–113].

of Results.We establish that several problems are highly parallelizable.For each of these problems, we design an optimal 0 (loglogn ) time parallel algorithm on the Common CRCW PRAM model which is the weakest among the CRCW PRAM models.These problems include: 0 all nearest smaller values, l preprocessing for answering range maxima queries, l several problems in Computational Geometry, l string matching.