A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
<|reference_start|>A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm: 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.<|reference_end|>
@article{lecroq2024a,
    title={A fast implementation of the good-suffix array for the Boyer-Moore
  string matching algorithm},
    author={Thierry Lecroq},
    journal={arXiv preprint arXiv:2402.16469},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16469},
    primaryClass={cs.DS}
}