| Título: | Average complexity of exact and approximate multiple string matching |
| Autores: |
Navarro, Gonzalo Fredriksson, Kimmo |
| Fecha: |
2007-04-18 2007-04-18 2004-08-16 |
| Publicador: | ELSEVIER |
| Fuente: |
Ver documento |
| Tipo: | Artículo de Revista |
| Tema: |
lower bounds Yao's bound |
| Descripción: | 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. |
| Idioma: | Inglés |