UNSPECIFIED (1995) TIGHTER LOWER BOUNDS ON THE EXACT COMPLEXITY OF STRING-MATCHING. SIAM JOURNAL ON COMPUTING, 24 (1). pp. 30-45. ISSN 0097-5397

Full text not available from this repository.

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
Date:	February 1995
Volume:	24
Number:	1
Number of Pages:	16
Page Range:	pp. 30-45
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/20028

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item