Searching with Extended Guard and Pivot Loop

Waltteri Pakalen, Jorma Tarhio, Bruce Watson

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


We explore practical optimizations on comparison-based exact string matching algorithms. We present a guard test that compares q-grams between the pattern and the text before entering the match loop, and evaluate experimentally the benefit of optimization of this kind. As a result, the Brute Force algorithm gained most from the guard test, and it became faster than many other algorithms for short patterns. In addition, we present variations of a recent algorithm that uses a special skip loop where a pivot, a selected position of the pattern, is tested at each alignment of the pattern and in case of failure; the pattern is shifted based on the last character of the alignment. The variations include alternatives for the pivot and the shift function. We show the competitiveness of the new algorithm variations by practical experiments.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2021
EditorsJan Holub, Jan Zdarek
PublisherCzech Technical University
ISBN (Print)978-80-01-06869-4
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 30 Aug 202131 Aug 2021


ConferencePrague Stringology Conference
Country/TerritoryCzech Republic
Internet address


  • exact string matching
  • tune-up of algorithms
  • guard test
  • skip loop
  • experimental comparison


Dive into the research topics of 'Searching with Extended Guard and Pivot Loop'. Together they form a unique fingerprint.

Cite this