The Library
TIGHTER LOWER BOUNDS ON THE EXACT COMPLEXITY OF STRING-MATCHING
Tools
UNSPECIFIED (1995) TIGHTER LOWER BOUNDS ON THE EXACT COMPLEXITY OF STRING-MATCHING. SIAM JOURNAL ON COMPUTING, 24 (1). pp. 30-45. ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
This paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about (1+9/4(m+1)).n character comparisons is obtained. For general algorithms, a lower bound of about (1+2/m+3).n character comparisons is obtained. These lower bounds complement an on-line upper bound of about (1+8/3(m+1)).n comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | SIAM JOURNAL ON COMPUTING | ||||
Publisher: | SIAM PUBLICATIONS | ||||
ISSN: | 0097-5397 | ||||
Official Date: | February 1995 | ||||
Dates: |
|
||||
Volume: | 24 | ||||
Number: | 1 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 30-45 | ||||
Publication Status: | Published |
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 |