Home // PATTERNS 2010, The Second International Conferences on Pervasive Patterns and Applications // View article
Authors:
Stephen Fulwider
Amar Mukherjee
Keywords: string matching, approximate string matching, multiple approximate string matching.
Abstract:
In this paper, we consider certain generalizations of string matching problems. The multiple pattern matching problem is that of finding all occurrences of a set of patterns in a fixed text. This is a well studied problem, and several popular Unix utilities (grep, agrep, and nrgrep, to name a few) implement a host of algorithms to solve this problem. In this paper, we present both exact and approximate multiple pattern matching, using a uniform paradigm that generalizes the Shift-AND method of Baeza-Yates and Gonnet. Our algorithm is able to achieve better performance in certain searching scenarios when compared with the Unix utilities agrep and nrgrep, and should be considered being added to the grep family of searching algorithms.
Pages: 78 to 83
Copyright: Copyright (c) IARIA, 2010
Publication date: November 21, 2010
Published in: conference
ISSN: 2308-3557
ISBN: 978-1-61208-111-3
Location: Lisbon, Portugal
Dates: from November 21, 2010 to November 26, 2010