Logo image
Back
An adaptive hybrid pattern-matching algorithm on indeterminate strings
Journal article   Open access   Peer reviewed

An adaptive hybrid pattern-matching algorithm on indeterminate strings

W.F. Smyth and S. Wang
International Journal of Foundations of Computer Science, Vol.20(6), pp.985-1004
2009
DOI: https://doi.org/10.1142/S0129054109007005
pdf
patternmatching.pdfDownloadView
Author’s Version Open Access
url
Link to Published Version *Subscription may be requiredView

Abstract

We describe a hybrid pattern-matching algorithm that works on both regular and indeterminate strings. This algorithm is inspired by the recently proposed hybrid algorithm FJS and its indeterminate successor. However, as discussed in this paper, because of the special properties of indeterminate strings, it is not straightforward to directly migrate FJS to an indeterminate version. Our new algorithm combines two fast pattern-matching algorithms, ShiftAnd and BMS (the Sunday variant of the Boyer-Moore algorithm), and is highly adaptive to the nature of the text being processed. It avoids using the border array, therefore avoids some of the cases that are awkward for indeterminate strings. Although not always the fastest in individual test cases, our new algorithm is superior in overall performance to its two component algorithms — perhaps a general advantage of hybrid algorithms.

Details

Metrics

216 File views/ downloads
54 Record Views
16 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1103 Efficient Algorithms
Web Of Science research areas
Computer Science, Theory & Methods
ESI research areas
Computer Science
Logo image