A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929256705032192 |
|---|---|
| author | Lecroq, Thierry |
| author_facet | Lecroq, Thierry |
| contents | String matching is the problem of finding all the occurrences of a pattern in a text. It has been intensively studied and the Boyer-Moore string matching algorithm is probably one of the most famous solution to this problem. This algorithm uses two precomputed shift tables called the good-suffix table and the bad-character table. The good-suffix table is tricky to compute in linear time. Text book solutions perform redundant operations. Here we present a fast implementation for this good-suffix table based on a tight analysis of the pattern. Experimental results show two versions of this new implementation are the fastest in almost all tested situations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16469 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm Lecroq, Thierry Data Structures and Algorithms E.1 String matching is the problem of finding all the occurrences of a pattern in a text. It has been intensively studied and the Boyer-Moore string matching algorithm is probably one of the most famous solution to this problem. This algorithm uses two precomputed shift tables called the good-suffix table and the bad-character table. The good-suffix table is tricky to compute in linear time. Text book solutions perform redundant operations. Here we present a fast implementation for this good-suffix table based on a tight analysis of the pattern. Experimental results show two versions of this new implementation are the fastest in almost all tested situations. |
| title | A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm |
| topic | Data Structures and Algorithms E.1 |
| url | https://arxiv.org/abs/2402.16469 |