EFFICIENT STRING-MATCHING ON PACKED TEXTS

The so called ''four Russians technique'' is often used to speed up al gorithms by packing several data items in a single memory cell. Given a sequence of n symbols over a constant size alphabet, one can pack th e sequence into O(n/lambda) memory cells in O(log lambda) time using n /log lambda processors, where lambda is the number of symbols packed i nto one memory word. Given a pattern of length m and a text of length n, this paper presents an efficient CRCW-PRAM string-matching algorith m for packed strings that takes O(log log (m/lambda)) time and perform s O(n/lambda) operations for lambda = O(log n), an improvement by a fa ctor of lambda on the number of operations used in previous algorithms . Using this string-matching algorithm one can test if a string is squ are-free and find all palindromes in a string in O(log log n) time usi ng n/log log n processors.