Efficient String Matching on Coded Texts

Dany Breslauer
Leszek Gasieniec

December 1994


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 tex2html_wrap_inline24 memory cells in tex2html_wrap_inline26 time using tex2html_wrap_inline28 processors. This paper presents an efficient CRCW-PRAM string-matching algorithm for coded texts that takes tex2html_wrap_inline30 time making only tex2html_wrap_inline24 operations, an improvement by a factor of tex2html_wrap_inline34 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 tex2html_wrap_inline36 time using tex2html_wrap_inline38 processors.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.