Average complexity of exact and approximate multiple string matching

Author	dc.contributor.author	Navarro, Gonzalo
Author	dc.contributor.author	Fredriksson, Kimmo	es_CL
Admission date	dc.date.accessioned	2007-04-18T21:47:40Z
Available date	dc.date.available	2007-04-18T21:47:40Z
Publication date	dc.date.issued	2004-08-16
Cita de ítem	dc.identifier.citation	THEORETICAL COMPUTER SCIENCE 321 (2-3): 283-290 AUG 16 2004	en
Identifier	dc.identifier.issn	0304-3975
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/124528
Abstract	dc.description.abstract	We show that the average number of characters examined to search for r random patterns of length m in a text of length n over a uniformly distributed alphabet of size a cannot be less than Omega(n log(sigma)(rm)/m). When we permit up to k insertions, deletions, and/or substitutions of characters in the occurrences of the patterns, the lower bound becomes Omega(n(k + log(sigma)(rm))/m). This generalizes previous single-pattern lower bounds of Yao (for exact matching) and of Chang and Marr (for approximate matching), and proves the optimality of several existing multipattern search algorithms.	en
Lenguage	dc.language.iso	en	en
Publisher	dc.publisher	ELSEVIER	en
Keywords	dc.subject	lower bounds	en
Título	dc.title	Average complexity of exact and approximate multiple string matching	en
Document type	dc.type	Artículo de revista