Open AccessEfficient String Matching on Coded Texts
Author(s) -
Dany Breslauer
Publication year - 1994
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v1i42.21600
Subject(s) - lambda , string (physics) , string searching algorithm , alphabet , binary logarithm , sequence (biology) , combinatorics , palindrome , mathematics , log log plot , auxiliary memory , encode , matching (statistics) , pattern matching , algorithm , arithmetic , discrete mathematics , computer science , physics , statistics , optics , mathematical physics , biology , genetics , biochemistry , programming language , computer hardware , gene , philosophy , linguistics , chemistry , crispr
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. 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.