Efficient String Matching on Coded Texts
Dany Breslauer December 1994 |
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. |