String matching is the problem of finding all the substrings of a text which match a given pattern. It is one of the most investigated problems in computer science, mainly due to its very diverse applications in several fields. Recently, much research in the string matching field has focused on the efficiency and flexibility of the searching procedure and quite effective techniques have been proposed for speeding up the exist- ing solutions. In this context, algorithms based on factors recognition are among the best solutions. In this paper, we present a simple and very efficient algorithm for string matching based on a weak factor recognition and hashing. Our algorithm has a quadratic worst-case running time. However, despite its quadratic complexity, experimental results show that our algorithm obtains in most cases the best running times when compared, un- der various conditions, against the most effective algorithms present in literature. In the case of small alphabets and long patterns, the gain in running times reaches 28%. This makes our proposed algorithm one of the most flexible solutions in practical cases.

Cantone D., Faro S., Pavone A. (2017). Speeding up string matching by weak factor recognition. In Proceedings of the Prague Stringology Conference 2017 (pp. 42-50).

Speeding up string matching by weak factor recognition

Pavone A.
2017-01-01

Abstract

String matching is the problem of finding all the substrings of a text which match a given pattern. It is one of the most investigated problems in computer science, mainly due to its very diverse applications in several fields. Recently, much research in the string matching field has focused on the efficiency and flexibility of the searching procedure and quite effective techniques have been proposed for speeding up the exist- ing solutions. In this context, algorithms based on factors recognition are among the best solutions. In this paper, we present a simple and very efficient algorithm for string matching based on a weak factor recognition and hashing. Our algorithm has a quadratic worst-case running time. However, despite its quadratic complexity, experimental results show that our algorithm obtains in most cases the best running times when compared, un- der various conditions, against the most effective algorithms present in literature. In the case of small alphabets and long patterns, the gain in running times reaches 28%. This makes our proposed algorithm one of the most flexible solutions in practical cases.
2017
Settore INF/01 - Informatica
978-80-01-06193-0
Cantone D., Faro S., Pavone A. (2017). Speeding up string matching by weak factor recognition. In Proceedings of the Prague Stringology Conference 2017 (pp. 42-50).
File in questo prodotto:
File Dimensione Formato  
Pubblicazione 2017-PSC.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 171.78 kB
Formato Adobe PDF
171.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/640833
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact