The Practical Efficiency of Convolutions in Pattern Matching Algorithms

Issue title: Workshop on Combinatorial Algorithms

Article type: Research Article

Authors: Amir, Amihood | Levy, Avivit | Reuveni, Liron

Affiliations: Department of Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel. E-mails: amir@cs.biu.ac.il; avivlev@netvision.net.il; lironr@ashdot-a.org.il

Abstract: Convolutions have proven to be an effective tool in asymptotically efficient pattern matching algorithms. This study attempts to find the type of problems where convolutions are inefficient in practice, and give possible solutions for the complex cases where the convolution method does not seem to aid realistic sized inputs.

Journal: Fundamenta Informaticae, vol. 84, no. 1, pp. 1-15, 2008