Three Strategies for the Dead-Zone String Matching Algorithm

Authors Organisations
  • Jacqueline Daykin(Author)
  • Richard Groult(Author)
    University of Picardie Jules Verne
  • Yannick Guesnet(Author)
    University of Rouen
  • Thierry Lecroq(Author)
    University of Rouen
  • Arnaud Lefebvre(Author)
    University of Rouen
  • Martine Léonard(Author)
    University of Rouen
  • Laurent Mouchard(Author)
    University of Rouen
  • Élise Prieur-Gaston(Author)
    University of Rouen
  • Bruce Watson(Author)
    University of Pretoria
    Stellenbosch University
    Centre for Artificial Intelligence Research
Type Paper
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
CountryCzech Republic
CityPrague
Period27 Aug 201828 Aug 2018
Links
Permanent link
View graph of relations
Citation formats

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