Average complexity of exact and approximate multiple string matching

详细信息    查看全文

• 作者：Navarro ; Gonzalo ; Fredriksson ; Kimmo
• 关键词：Lower bounds ; Yao's bound ; String matching allowing differences ; Multipattern matching
• 刊名：Theoretical Computer Science
• 出版年：2004
• 出版时间：August 16, 2004
• 年：2004
• 卷：321
• 期：2-3
• 页码：283-290
• 全文大小：194 K

文摘

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 σ cannot be less than Ω(nlog_σ(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 Ω(n(k+log_σ(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.