An adaptive hybrid pattern-matching algorithm on indeterminate strings
MetadataShow full item record
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.
Electronic version of an article published as International Journal of Foundations of Computer Science, 20, 6, 2009, 985-1004. http://dx.doi.org/10.1142/S0129054109007005 © copyright World Scientific Publishing Company
Showing items related by title, author, creator and subject.
Smyth, Bill; Wang, Shu; Yu, Mao (2008)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 . ...
Smyth, Bill; Wang, S. (2009)We first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a "wild card", a "don't-care" or an "indeterminate letter" in the literature). The proof is modelled on Euclid's ...
Barton, C.; Iliopoulos, Costas; Pissis, S. (2014)Background: Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist ...