@article{Breslauer_1994, title={Efficient String Matching on Coded Texts}, volume={1}, url={https://tidsskrift.dk/brics/article/view/21600}, DOI={10.7146/brics.v1i42.21600}, abstractNote={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 / lambda) memory cells in O(log(lambda) ) time using n / log(lambda) processors.<br /> <br />This paper presents an efficient CRCW-PRAM string-matching algorithm for coded texts that takes O(log log(m/lambda)) time making only O(n / lambda ) operations, an improvement by a factor of lambda = O(log n) 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 O(log log n) time using n / log log n processors.}, number={42}, journal={BRICS Report Series}, author={Breslauer, Dany}, year={1994}, month={Dec.} }