Three Strategies for the Dead-Zone String Matching Algorithm

Jacqueline W. Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, Arnaud Lefebvre, Martine Léonard, Laurent Mouchard, Élise Prieur-Gaston, Bruce Watson

Research output: Contribution to conferencePaperpeer-review

2 Citations (SciVal)

Abstract

Online exact string matching consists in locating all the occurrences of a pattern in a text where only the pattern can be preprocessed. Classical online exact string matching algorithms scan the text from start to end through a window whose size is equal to the pattern length. Exact string matching algorithms from the dead-zone family first locate the window in the middle of the text, compare the content of the window and the pattern and then recursively apply the same procedure on the left part and on the right part of the text while possibly excluding some parts of the text. We propose three different strategies for performing the symbol comparisons and, we compute the shifts for determining the left and right parts of the text at each recursive call
Original languageEnglish
Pages117–128
Publication statusPublished - 2018
EventPrague Stringology Conference 2018 - Czech Technical University, Prague, Czech Republic
Duration: 27 Aug 201828 Aug 2018

Conference

ConferencePrague Stringology Conference 2018
Country/TerritoryCzech Republic
CityPrague
Period27 Aug 201828 Aug 2018

Fingerprint

Dive into the research topics of 'Three Strategies for the Dead-Zone String Matching Algorithm'. Together they form a unique fingerprint.

Cite this