The Library
Detecting false matches in string-matching algorithms
Tools
UNSPECIFIED (1997) Detecting false matches in string-matching algorithms. In: Conference on Combinatorial Pattern Matching, PADOVA, ITALY, 1993. Published in: ALGORITHMICA, 18 (4). pp. 512-520. ISSN 0178-4617.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Consider a text string of length II, a pattern string of length I,I, and a match vector of length II which declares each location in the text to be either a mismatch (the pattern does not occur beginning at that location in the text) or a potential match (the pattern may occur beginning at that location in the text). Some of the potential matches could be false, i.e., the pattern may not occur beginning at some location in the text declared to be a potential match. We investigate the complexity of two problems in this context, namely, checking if there is any false match, and identifying all the false matches in the match vector.
We present an algorithm on the CRCW PRAM that checks if there exists a false match in O(1) time using O (rr) processors. This algorithm does not require preprocessing the pattern. Therefore, checking for false matches is provably simpler than string matching since string matching takes Omega (log log m) lime on the CRCW PRAM. We use this simple algorithm to convert the Karp-Rabin Monte Carlo type suing-matching algorithm into a Las Vegas type algorithm without asymptotic loss in complexity. We also present an efficient algorithm for identifying all the false matches and,as a consequence, show that string-matching algorithms take Omega(log log m) time even given the flexibility to output a few false matches.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | ALGORITHMICA | ||||
Publisher: | SPRINGER VERLAG | ||||
ISSN: | 0178-4617 | ||||
Official Date: | August 1997 | ||||
Dates: |
|
||||
Volume: | 18 | ||||
Number: | 4 | ||||
Number of Pages: | 9 | ||||
Page Range: | pp. 512-520 | ||||
Publication Status: | Published | ||||
Title of Event: | Conference on Combinatorial Pattern Matching | ||||
Location of Event: | PADOVA, ITALY | ||||
Date(s) of Event: | 1993 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |