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 deadzone 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.
Reference:
Daykin, J.W., Grout, R., Guesnet, G., Lecroq, T., Lefebvre, A., Léonard, L., Mouchard, L. & Prieur-Gaston, E. 2018. Three Strategies for the Dead-Zone String Matching Algorithm, pp. 117–128. Proceedings of PSC 2018, Jan Holub and Jan Zdˇ ’arek (Eds.), ISBN 978-80-01-06484-9 ´Czech Technical University in Prague, Czech Republic
Daykin, J., Groult, R., Guesnet, G., Lecroq, T., Lefebvre, A., Léonard, L., ... Watson, B. (2018). Three strategies for the dead-zone string matching algorithm. Prague Stringology Club. http://hdl.handle.net/10204/10937
Daykin, JW, R Groult, G Guesnet, T Lecroq, A Lefebvre, L Léonard, L Mouchard, E Prieur-Gaston, and Bruce Watson. "Three strategies for the dead-zone string matching algorithm." (2018): http://hdl.handle.net/10204/10937
Daykin J, Groult R, Guesnet G, Lecroq T, Lefebvre A, Léonard L, et al, Three strategies for the dead-zone string matching algorithm; Prague Stringology Club; 2018. http://hdl.handle.net/10204/10937 .
Presented at: Proceedings of the Prague Stringology Conference 2018, Prague, Czech Republic, 29-31 August 2018. Due to copyright restrictions, the attached PDF file only contains the abstract of the full-text item. For access to the full-text item, please consult the publisher's website. While waiting for the post-print or published PDF document from the publisher