Accession Number : ADA267758


Title :   Fast Parallel String Prefix-Matching


Descriptive Note : Technical rept.,


Corporate Author : COLUMBIA UNIV NEW YORK DEPT OF COMPUTER SCIENCE


Personal Author(s) : Breslauer, Dany


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267758.pdf


Report Date : Jan 1992


Pagination or Media Count : 10


Abstract : An 0(loglogm) time nlogm/loglogm-processor CRCW-PRAM algorithm for the string prefix-matching problem over a general alphabet is presented. The algorithm can also be used to compute the KMP failure function in 0(loglogm) time on mlogm/loglogm processors. These results improve on the running time of the best previous algorithm for both problems, which was 0 (log m), while preserving the same number of operations.


Descriptors :   *PARALLEL PROCESSING , *PATTERNS , *MATCHING , ALGORITHMS , ALPHABETS , TIME , OPERATION , FAILURE


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE