Access Restriction

Author Kim, Sun
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract In this paper, we present a new string-pattern matching algorithm that partitions the text into segments of the input pattern length and searches for pattern occurrences using a simple hashing scheme. Unlike the well known Boyer-Moore style algorithm, our algorithm does not compute variable shift length, thus providing a conceptually simpler way to search for patterns. Empirical evaluation shows that our algorithm runs significantly faster than Sunday's and Horspool's extensions of the Boyer-Moore algorithm. The notion of the non-occurrence heuristic used in our algorithm, together with a text partitioning scheme, leads to a simplified scheme for searching for pattern occurrences, thus yielding better run time performance.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 4

Open content in new tab

   Open content in new tab
Source: ACM Digital Library