Efficient string matching on coded texts

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 O(n/A) memory cells in O(log A) time using n~ log A processors. This paper presents an efficient CRCW-PRAM string-matching algorithm for coded texts that takes O(loglog(m/),)) time⁴ making only O(n/A) operations, an improvement by a factor of A --- O(log n) on the number of operations used in previous algorithms. Using this stringmatching algorithm one can test if a string is square-free and find all palindromes in a string in O(log log n) time using n~ log log n processors.