An adaptive hybrid pattern-matching algorithm on indeterminate strings
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 [11] and its indeterminate successor [15]. However, as discussed in this paper, because of the special properties of indeterm...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
PSC
2008
|
| Online Access: | http://www.stringology.org/event/2008/p09.html http://hdl.handle.net/20.500.11937/15232 |
| _version_ | 1848748838305660928 |
|---|---|
| author | Smyth, Bill Wang, Shu Yu, Mao |
| author2 | Jan Holub |
| author_facet | Jan Holub Smyth, Bill Wang, Shu Yu, Mao |
| author_sort | Smyth, Bill |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 [11] and its indeterminate successor [15]. 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 variantof 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. |
| first_indexed | 2025-11-14T07:11:24Z |
| format | Conference Paper |
| id | curtin-20.500.11937-15232 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:11:24Z |
| publishDate | 2008 |
| publisher | PSC |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-152322022-11-21T06:47:04Z An adaptive hybrid pattern-matching algorithm on indeterminate strings Smyth, Bill Wang, Shu Yu, Mao Jan Holub Jan Zdarek 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 [11] and its indeterminate successor [15]. 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 variantof 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. 2008 Conference Paper http://hdl.handle.net/20.500.11937/15232 http://www.stringology.org/event/2008/p09.html PSC restricted |
| spellingShingle | Smyth, Bill Wang, Shu Yu, Mao An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title | An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title_full | An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title_fullStr | An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title_full_unstemmed | An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title_short | An adaptive hybrid pattern-matching algorithm on indeterminate strings |
| title_sort | adaptive hybrid pattern-matching algorithm on indeterminate strings |
| url | http://www.stringology.org/event/2008/p09.html http://hdl.handle.net/20.500.11937/15232 |