文章基本信息

标题：Efficient String Matching on Coded Texts
本地全文：下载
作者：Dany Breslauer
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1994
卷号：1
期号：42
出版社：Aarhus University
摘要：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.