strsearch - Rassegna di algoritmi di ricerca di stringhe
--------------------------------------------------------

Un piccolo programma che confronta quattro algoritmi classici di
string matching esatto su un buffer di prova, misurandone i tempi:

  BF   Brute Force
  KMP  Knuth-Morris-Pratt
  BM   Boyer-Moore (bad-character + good-suffix)
  QS   Quick Search (variante semplificata di Boyer-Moore)

Compilazione:

  cc -O2 -o strsearch strsearch.c

Esecuzione:

  ./strsearch

Il programma riempie un buffer di 2 MB, vi nasconde in un punto casuale
una frase contenente il pattern da cercare, poi esegue a turno i quattro
algoritmi stampando per ciascuno gli offset trovati e il tempo impiegato.

Nota: su un buffer a bassa entropia come questo il Brute Force e'
spesso competitivo o piu' veloce, perche' quasi ogni confronto fallisce
al primo carattere. Il vantaggio di Boyer-Moore e Quick Search cresce
con testi reali, alfabeti piu' ampi e pattern piu' lunghi.

Le implementazioni degli algoritmi seguono la nomenclatura del
riferimento classico di C. Charras e T. Lecroq, "Handbook of Exact
String Matching Algorithms". La raccolta e la funzione di benchmark
sono di Giuseppe Caulo.

Questo codice ha scopo puramente didattico.
