Abstract:
The so called ``four Russians technique'' is often used to
speed up algorithms by encoding several data items in a single memory cell.
Given a sequence of n symbols over a constant size alphabet, one can encode
the sequence into 
memory cells in 
time
using 
processors. This paper presents an efficient
CRCW-PRAM string-matching algorithm for coded texts that takes 
time making only operations, an improvement by
a factor of 
on the number of operations used in
previous algorithms. Using this string-matching algorithm one can test if a
string is square-free and find all palindromes in a string in 
time using 
processors.
Available as PostScript, PDF, DVI.