1 Algoritmo ingenuo Algoritmo ingenuo Algoritmo ingenuo Algoritmo ingenuo Algoritmi e Laboratorio a.a. 2009-10 Lezioni Il problema

(1)

Università di Torino – Facoltà di Scienze MFN Corso di Studi in Informatica Curriculum SR (Sistemi e Reti)

Algoritmi e Laboratorio a.a. 2009-10 Lezioni

prof. Elio Giovannetti Lezione 39 – String matching.

versione 03/02/10

Quest' opera è pubblicata sotto una Licenza Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

Il problema

• Dato un testo, che possiamo idealmente pensare come una (lunga) stringa t, e data una (molto più corta) stringa s, trovare – se esiste – il posto in cui scompare in t.

• Nota: la stringa da cercare viene anche chiamata pattern.

• Esempio. La classe Stringdi Java possiede un metodo int indexOf(String str) che restituisce l’indice di

03/02/10 17.25 E. Giovannetti - AlgELab-09-10 - Lez.39 2

g

inizio della prima occorrenza della sottostringa strnella stringa this(oppure -1 se strnon compare).

• Esaminiamo due algoritmi risolventi per tale problema.

Algoritmo ingenuo

Si fa scorrere sul testo la stringa da cercare o pattern, e dopo ogni tentativo fallito si sposta la stringa esattamente di una posizione nel testo.

Esempio:

Trovare la sottostringa “aab” nel testo “aaaaaaab”.

a a a a a a a b

a a a a a a a b a a b

Algoritmo ingenuo

Si fa scorrere sul testo la stringa da cercare, e dopo ogni tentativo fallito si sposta la stringa esattamente di una posizione nel testo.

Esempio:

a a a a a a a b

Algoritmo ingenuo

Esempio:

a a a a a a a b

Algoritmo ingenuo

Esempio:

a a a a a a a b

(2)

Algoritmo ingenuo

Esempio:

a a a a a a a b

Algoritmo ingenuo

Esempio:

a a a a a a a b

a a b TROVATO !

Nota

Se si spostasse la stringa di più di una posizione nel testo, si potrebbe perdere una presenza della stringa nel testo.

Esempio:

a a a b c d e f a a b

Se avendo ottenuto un mismatch fra a e b spostassi la

Se, avendo ottenuto un mismatch fra a e b, spostassi la stringa “aab” direttamente al punto nel testo in cui si è avuto il mismatch, cioè:

a a a b c d e f a a b

perderei il riconoscimento della stringa.

Invariante

(sono necessari due indici, ma è comodo tenerne tre)

0 k i n-1

significato degl’indici:

j m-1 s:

t:

significato degl indici:

•k: indice del carattere iniziale del prefisso del pattern riconosciuto nel testo;

•i: indice del prossimo carattere da esaminare nel testo;

•j: indice del prossimo carattere del pattern;

Invariante

(sono necessari due indici, ma è comodo tenerne tre)

0 k i n-1

t[k .. i-1] = s[ 0.. j-1]

la stringa sè stata riconosciuta nel testo ta partire dalla j m-1

s:

t:

g p

posizione k, per i primi jcaratteri della stringa; iè l’indice del successivo carattere da esaminare nel testo.

Corpo del ciclo

•caso t[i] == s[j]: anche il nuovo carattere va bene, quindi: i++; j++;

•caso t[i] != s[j]: bisogna ricominciare il confronto dall’inizio di s, spostandosi a destra di uno nel testo, quindi

k++; i = k; j = 0;

Test del while

Si deve uscire se:

0 k i n-1

j m-1 s:

t:

Si deve uscire se:

•j == m: si è riconosciuta l’intera stringa s, iniziante da k;

oppure

•i == n: si è arrivati alla fine del testo.

Quindi il ciclo deve continuare (pensa anche a de Morgan) se i < n e j < m:

while(i < n && j < m)

(3)

static int search(String str, String text) { char[] s = str.toCharArray();

char[] t = text.toCharArray();

int m = s.length, n = t.length;

int i = 0, j = 0, k = 0;

while(i < n && j < m) { if(t[i] == s[j]) {

i++; j++;

} else {

k++; i = k; j = 0;

} }

return j == m ? k : -1;

}

Complessità del caso peggiore.

mconfronti con la stringa in posizione k, ripetuti nvolte (in realtà n-m+1volte):

T(n) = Θ(m •n) Esempio:

Nell’esempio precedente, stringa “aab” nel testo “aaaaaaab”, si operano 6 (= 8 – 3 + 1) volte 3 confronti, cioè 18 confronti.

Se si fa crescere mproporzionalmente a n, si ha ovviamente T(n) = Θ(n²)

(algoritmo quadratico)

Si può fare meglio ?

Verso un miglioramento: esempio.

• Dopo aver riconosciuto la stringa “conte” e aver fallito sul carattere successivo, è inutile spostare la stringa di un solo

l i è

c o n t e n t i c o n t e s s a

s s i m o _ e _

carattere nel testo, cioè:

perché i 4 successivi caratteri del testo, cioè “onte”, sono già noti, e non si accordano con “cont”.

s s i m o _ e _

Esempio (fine)

Ma è anche inutile spostare la stringa di due posizioni nel testo, cioè:

s s i m o _ e _

perché i 3 successivi caratteri del testo, cioè “nte”, sono già

ti i d “ ”

noti, e non si accordano con “con”.

Analogamente per le tre posizioni successive. Si può quindi spostare la stringa direttamente di 5 posizioni nel testo, sul primo carattere non riconosciuto:

c o n t e n t i

c o n t e s s a s s i m o _ e _

Osservazione

Far scorrere il pattern “contessa” di kposizioni nel testo equivale a far scorrere il sotto-pattern “conte” di kposizioni rispetto a se stesso !

s s i m o _ e _

Potremmo quindi determinare a priori quando tale scorrimento è sicuramente destinato al fallimento !

Altro esempio

Anche qui, è inutile spostare il pattern di 1, 2, o 3 posizioni, perché i primi 4 caratteri di abaab, cioè abaanon si accordano con gli ultimi 4, cioè baab; e così i primi 3 con gli

l i i 3 I i i i 2 i di b b i è b a b a a b b a b a b a a b a b a a b a a b a a b

ultimi 3. Invece i primi 2 caratteri di abaab, cioè ab, sono uguali ai due ultimi:

a b a a b a a b

Allora si può fa scorrere il pattern di 3 posti, e inoltre ricominciare i confronti non dall’inizio del pattern:

a b a a b b a b a b a a b a b a a b a a b a a b

(4)

L’idea dell’algoritmo.

• Nei due esempi precedenti non si ri-esaminano elementi del testo già esaminati, bensì si continua con il carattere non riconosciuto del testo, eventualmente “tornando indietro”

nel pattern, ma non necessariamente all’inizio del pattern, in modo da non perdere un eventuale sotto-pattern già riconosciuto.

• Si può allora eseguire una pre-elaborazione che, esaminando il pattern da cercare, determini per ognuno dei possibili m fallimenti (secondo, terzo, …, m-esimo carattere del pattern) da quale carattere del pattern stesso occorre ripartire.

Riassunto

0 j-1 j

testo s:

Dopo il mismatch si può avere un nuovo matching del pattern

Dopo il mismatch, si può avere un nuovo matching del pattern che cominci nella parte di testo già esaminata solo se …

Riassunto

0 j-1 j testo s:

Riassunto

0 k j-1 j testo s:

Riassunto

0 k j-1 j testo s:

0 j-1 j s:

Riassunto

0 j-1 j testo s:

0 j-1 j s:

… quindi solo se esiste un ktale che:

s[0 .. k-1] = s[j-k .. j-1]

0 k j-k j-1 j s:

(5)

Che cosa deve produrre il pre-processing

Sia mla lunghezza del pattern s.

Per ogni j (con 1 ≤ j < m) bisogna pre-calcolare l’indice nel pattern da cui ricominciare la scansione se s[j]non è uguale al carattere t[i]letto nel testo, memorizzando tale valore in un array b. È conveniente che l’array bsia di dimensione m, in modo che:

b[j] = indice knel pattern da cui ricominciare la scansione b[j] = indice knel pattern da cui ricominciare la scansione se s[j]non è uguale al carattere t[i]letto nel testo.

L’elemento b[0]per ora possiamo considerarlo una cella

“sprecata”, perché non utilizzata dall’algoritmo di ricerca vero e proprio.

In realtà – come vedremo – fissandone il valore in modo opportuno essa sarà usata per rendere più semplice il codice del preprocessing.

Nota Bene

Il caso in cui serve il preprocessing è quello in cui il matching del pattern col testo fallisce dopo il primo carattere del pattern da cercare.

In tal caso si riprende la scansione del pattern dal kpre- calcolato, mentre l’indice inel testo non viene incrementato, poiché bisogna confrontare con s[k]lo stesso carattere t[i]

che aveva causato il mismatching con s[j]

Se invece il mismatching avviene col primo carattere del pattern, cioè per j = 0, bisogna invece in ogni caso avanzare nel testo di 1 carattere e naturalmente ricominciare la scansione del pattern da 0.

Esempio

array prodotto dal

preprocessing: ? 0 0 0 1 2 3 b a r b a r a stringa da trovare

(o pattern):

0 1 2 3 4 5 6

b a r b a r b a r a testo:

Il matching fallisce sul carattere di indice 6del pattern:

si ricomincia a scandire il pattern dall’indice 3.

b a r b a r a testo: b a r b a r b a r a

b a r b a r a

0 1 2 3 4 5 6

La procedura di ricerca in Java: il ciclo.

static int KMPsearch(String str, String text) { int m = str.length(), n = text.length();

int[] b = preprocess(s);

int i = 0, j = 0;

while(i < n && j < m) {

if(text.charAt(i) == str.charAt[j]) { j++; i++; match riuscito del carattere:

} si l tt h l t st

} avanzo sia nel pattern che nel testo else if(j == 0) i++; mismatch con il primo caratt.

di str : avanzo nel testo.

else j = b[j]; mismatch con un car. (non il primo) di str: sto fermo nel testo e riparto su strdall’indice pre-calcolato }

...

Uscita dal ciclo e risultato

Due casi:

• si è usciti dal ciclo con j < m, cioè senza aver riconosciuto tutto il pattern; allora è evidentemente i = n, cioè il testo è finito e il pattern snon è stato trovato: restituisco -1.

• si è usciti dal ciclo perché (o con) j = m, cioè avendo riconosciuto l’intero pattern: restituisco la posizione (cioè l’indice del primo carattere) del pattern nel testo, i – m.n c pr mo caratt r ) patt rn n t sto, m.

La procedura

(trasformando per efficienza la stringa-pattern in un array di caratteri, cosa comunque non indispensabile)

static int KMPsearch(String str, String text) { int m = str.length(), n = text.length();

char[] s = str.toCharArray();

int[] b = preprocess(s);

int i = 0, j = 0;t , j ; while(i < n && j < m) {

if(text.charAt(i) == s[j]) {j++; i++;}

else if(j == 0) i++;

else j = b[j];

}

return (j < m) ? -1 : i-m;

}

(6)

Il preprocessing.

Alcune necessarie definizioni preliminari.

• prefissodi una stringa c₀c₁… c_m-1:

è una sottostringa iniziale (eventualmente vuota) c₀… c_k-1 (con 0 ≤ k ≤ m) della stringa; kè la lunghezza del prefisso.

• suffissodi una stringa c₀c₁… c_m-1:

è una sottostringa finale (eventualmente vuota) c_m-k… c_m-1 con 0 ≤ k ≤ mdella stringa; kè la lunghezza del suffisso.

• prefisso o suffisso proprio:prefisso o suffisso proprio è un prefisso o suffisso che è un prefisso o suffisso che non coincide con l’intera stringa (è più corto), cioèk < m;

• bordodi una stringa s: è una sottostringa che è allo stesso tempo prefisso proprio e suffisso proprio di s.

Note: la stringa vuota è un bordo di qualunque stringa;

la stringa vuota non ha bordo.

Esempio: I bordi della stringa “abacab” sono “” e “ab”; i bordi di “aaaa” sono: “”, “a”, “aa”, “aaa”.

Ricorda:

Il matching fallisce al k-esimo carattere del pattern: allora si deve spostare il pattern finché un “prefisso proprio” del pattern viene a coincidere con un suffisso (proprio) della parte riconosciuta del pattern (parte gialla): in questo caso il

parte riconosciuta del pattern (parte gialla): in questo caso il prefisso/suffisso è “ab”.

Ma un prefisso (proprio) coincidente con un suffisso è un bordo: bisogna quindi trovare il più lungo bordo della parte riconosciuta del pattern: il più lungo bordo di “abaab” è “ab”.

Che cosa deve produrre il pre-processing

Sia mla lunghezza del pattern s.

Per ogni j (con 1 ≤ j < m) bisogna pre-calcolare la lunghezza del massimo bordo del sottopattern s[0 .. j-1] , costruendo un array bdi dimensione m, dove:

b[j] = indice nel pattern da cui ricominciare la scansione se s[j]non è uguale al carattere

l l

letto nel testo.

= lunghezza del più lungo bordo di s[0 .. j-1]

Esempio

è il carattere del pattern su cui si

h i h

stringa da trovare

(o pattern): a b c d a b c

0 1 2 3 4 5 6 7 8

a d array prodotto dal

preprocessing: 0 0 0 0 1 2 3 1

0 1 2 3 4 5 6 7 8

a b

a b c ha mismatch

03/02/10 17.25 35

a b c a b c d a b c d a a b c d a b a b c d a b c a b c d a b c a

Due teoremi preliminari (dimostrazioni ovvie).

1. Se s[0 .. h] è un bordo non vuoto di s[0 .. k], allora

• s[0 .. h-1] è un bordo (eventualmente vuoto) di s[0 .. k-1],

• s[h] = s[k] .

0 h-1 h k-1 k

2. Se b1 eb2 sono due bordi di una stringa s, con b2più corto di b1, allora b2è anche un bordo di b1.

b1 b1

b2 b2 b2 b2

(7)

Nota terminologica a proposito del Teorema 1.

Un bordo s[0 .. h-1] di s[0 .. k-1]tale che s[h] = s[k] si dice che è un bordo estensibile (da bordo di s[0 .. k-1] a bordo di s[0 ..k]).

Il bordo s[0 .. h]si dice estensione del bordo s[0 .. h-1] . Il Teorema 1 si può allora formulare così:

Un bordo non vuoto di s[0 k]è l’estensione di un bordo Un bordo non vuoto di s[0 .. k]è l estensione di un bordo estensibiledi s[0 .. k-1].

0 k-1 k

Il preprocessing: l’invariante del ciclo esterno.

INVARIANTE (significato degl’indici):

• jè l’indice dell’ultimo elemento di bche è stato calcolato;

0 j

b: k

s:

0 k-1 j-1 j

j

• quindi se chiamiamo kil valore di b[j],

kè la lunghezza del più lungo bordo di s[0 .. j-1], cioè s[0 .. k-1]è il più lungo bordo dis[0 .. j-1].

Analogamente, per i precedenti elementi di bsi ha:

• se k1=b[j-1], s[0 .. k1-1]è il più lungo bordo dis[0 .. j-2];

• se k₂=b[j-2], s[0 .. k₂-1]è il più lungo bordo dis[0 .. j-3];

• ... ecc.

Il preprocessing: l’invariante del ciclo esterno.

INVARIANTE (in altre parole):

per ogni h ≤ j,

b[h]è l l h k d l iù l b d di [0 h 1]

0 j

b: k

s:

0 k-1 j-1 j

b[h]è la lunghezza k_hdel più lungo bordo di s[0 .. h-1], cioè s[0 .. k_h-1] è il più lungo bordo di s[0 .. h-1].

In particolare, per h = j:

b[j]è il valore ktale che

s[0 .. k-1]è il più lungo bordo di s[0 .. j-1].

Attenzione: diversamente dalla maggior parte degli algoritmi visti, jè scelto come l’indice dell’ultimo elemento calcolato, NON del successivo elemento da calcolare ! ,E 39

Il ciclo esterno

Attenzione: poiché j è l’ultimo elemento calcolato, si deve uscire dal ciclo quando j = m-1, NON quando j = m.

for(int j = 0; j < m-1; j++) {

k = b[j]; // lunghezza del più lungo bordo di s[0 .. j-1]

calcolata nel passo precedente;

devo trovare il più lungo bordo di s[0 j]

devo trovare il più lungo bordo di s[0 .. j]

allora cerco il più lungo bordo estensibile di s[0 .. j-1]

cioè cerco il più lungo bordo s[0 .. k-1] di s[0 .. j-1]

tale che s[k] =s[j];

la lunghezza del massimo bordo di s[0 .. j] è allora k+1:

b[j+1] = k+1;

}

Il preprocessing.

Inizializzazione

Come abbiamo visto, b[0]non è utilizzato dall’algoritmo di ricerca. Esso però potrà essere utilizzato, come vedremo, dall’algoritmo di preprocessing stesso.

All’interno di esso, poiché

b[h]è la lunghezza khdel più lungo bordo di s[0 .. h-1], allora

allora

b[0] è la lunghezza del più lungo bordo di s[0..-1], cioè la lunghezza del più lungo bordo del bordo vuoto.

Ma il bordo vuoto non ha bordi, quindi per indicare ciò poniamo b[0] = -1, il che sarà utile per la scrittura del codice.

Il corpo del ciclo, per calcolare b[j+1]

b[j+1] dovrà essere la lunghezza del max bordo di s[0 .. j]

Allora dobbiamo calcolare l’indice k’tale che s[0 .. k’]sia il più lungo bordo di s[0 .. j];

in b[j+1] dovrò poi mettere la sua lunghezza, che è k’+1.

• Per il Teorema 1, il più lungo bordo di di s[0 .. j]è l’estensione del più lungo bordo estensibile di di s[0 .. j-1]

oppure, se un tale bordo estensibile non esiste, il bordo pp , , vuoto.

E. Giovannetti - AlgELab-09-10 - Lez.39 42

0 j j+1

b: k k’

0 k’ k-1 k j-1 j s:

max bordo di s[0..j-1]

max. bordo estensibile di s[0..j-1]

(8)

Il ciclo interno.

• Per trovare tale bordo estensibile (o per scoprire che non esiste) bisogna fare, all’interno del ciclo principale, un ciclo annidato che generi, in ordine di lunghezza decrescente, tutti i bordi di s[0 .. j-1] , finché non ne trova uno estensibile, o finché non ci sono più bordi.

Il ciclo interno.

s[0..k-1] è il più lungo bordo di s[0..j-1]

0 k-1 k j-1 j s:

s[k] = s[j] ? se no, s[0..k-1] non è un bordo estensibile, bisogna provare con il bordo immediatamente più corto:

0 k’ j-1 j

s:

s[k’] = s[j] ? se no, s[0..k-1] non è un bordo estensibile, bisogna provare con il bordo ancora più corto

0 k’’ j-1 j s:

s[k’’] = s[j] ? se no, ecc.; se si, ho trovato !

Il ciclo interno

• Al passo generico, dato un bordo di s[0 .. j-1]:

• controlla se tale bordo è estensibile, e se non lo è trova il bordo più lungo fra i bordi di s[0 .. j-1] più corti del precedente;

• e così via finché si trova un bordo estensibile, o si scopre che un tale bordo non esiste.

• Per il Teorema 2, per cercare un bordo di s[0 .. j-1] più corto di quello dato, basta cercare un bordo del bordo dato:

• il bordo dato ha lunghezza k, allora il più lungo bordo di tale bordo ha lunghezza b[k];

• quindi si opera l’assegnazione k = b[k]

Attenzione: k = b[k]è l’istruzione chiave, e non è intuitiva !

Pittograficamente:

Supponiamo che il bordo giallodi s[0..j-1] non sia estensibile:

allora devo cercare un altro bordo di s[0..j-1], più corto, per vedere se è estensibile.

0 k-1 k j-1 j s:

Pittograficamente:

0 k-1 k j-1 j s:

Ma come faccio per trovare un bordo di s[0..j-1] più corto di quello giallo ?

Pittograficamente:

0 k-1 k j-1 j s:

Ma come faccio per trovare un bordo di s[0..j-1] più corto di quello giallo ?

Per il Teorema 2 basta che cerchi un bordo del bordo giallo ! Ma il più lungo bordo del prefisso giallo, cioè il più lungo bordo di s[0..k-1], è il valore di b[k]che è stato calcolato in uno dei passi precedenti.

Quindi faccio l’assegnazione k = b[k] !

(9)

Pittograficamente:

Controllo se questo più corto bordo di s[0..j-1]è estensibile, cioè se s[k] = s[j]. Ho i due casi:

• s[k] = s[j]: il bordo rosso di s[0..j-1]è estensibile ad un bordo di s[0 j] ho quindi trovato il più lungo bordo di s[0 j]

0 k j-1 j

s:

bordo di s[0..j], ho quindi trovato il più lungo bordo di s[0..j]

.

49

0 k j-1 j

s:

• s[k] ≠ s[j]: il bordo rosso s[0..j-1]non è estensibile: devo provare con un bordo di s[0..j-1]ancora più corto del bordo rosso: ma, sempre per il Teor.2, per trovarlo basta che cerchi un bordo del bordo rosso; ecc. 0 k j-1 j s:

Il corpo del ciclo interno

k = b[j];

while(kindica un prefisso && s[0 .. k-1] non estensibile) k = b[k];

Traducendo:

k = b[j];

while(k >= 0 && s[j] != s[k]) k = b[k];

All’uscita dal ciclo interno

• caso 1:

kè la lunghezza del più lungo bordo estensibile di s[0 .. j-1], quindi la lunghezza del più lungo bordo di s[0 .. j]è k+1: si esegue quindi l’istruzione

b[j+1] = k+1;

• caso 2:

un tale bordo non esiste, k = -1, quindi occorre ricominciare un tale bordo non esiste, k 1, quindi occorre ricominciare il matching del pattern dall’indice 0, cioè

b[j+1] = 0;

Ma poiché kè -1, ciò si ottiene, come nel caso precedente, con l’istruzione

b[j+1] = k+1;

Il preprocessing: l’algoritmo.

static int[] preprocess(char[] s) { int m = s.length;

int[] b = new int[m];

b[0] = -1; // al primo passo è k = -1, quindi int k; // il corpo del while non viene eseguito for(int j = 0; j < m-1; j++) {

k = b[j];

while(k >= 0 && s[j] != s[k]) k = b[k];

b[j+1] = k+1;

} // al primo passo si ottiene sempre b[1] = 0 return b;

}

Osserva: b[1]è la lunghezza del più lungo bordo di s[0 .. 0];

ma l’unico bordo di un segmento di lunghezza 1 è il bordo vuoto (lunghezza 0).

03/02/10 17.25 s:⁰ 52

Miglioramenti e semplificazioni.

Si può quindi inizializzare, oltre che b[0]a -1, anche b[1]a 0, e iniziare il ciclo esterno da j = 1 invece che da j = 0:

b[0] = -1; b[1] = 0;

int k;

for(int j = 1; j < m-1; j++) { k = b[j];

while(k >= 0 && s[j] != s[k]) k = b[k];

b[j+1] = k+1;

}

return b;

}

Miglioramenti e semplificazioni.

b[0] = -1; b[1] = 0;

int k;

for(int j = 1; j < m-1; j++) { k = b[j];

while(k >= 0 && s[j] != s[k]) k = b[k];

b[j+1] = k+1;

}

return b;

}

Si osservi che ad ogni iterazione il valore di b[j]calcolato nell’iterazione precedente è k+1; si può quindi semplificare il codice eliminando l’istruzione k = b[j] e incrementando k.

(10)

Miglioramenti e semplificazioni.

b[0] = -1; b[1] = 0;

int k = 0; int j = 1;

for(int j = 0; j < m-1; j++) {

while(k >= 0 && s[j] != s[k]) k = b[k];

b[j+1] = k+1;

k++;

}

return b;

}

Inoltre, invece di operare l’assegnazione b[j+1] = … e poi incrementare jnel ciclo for, si può usare un ciclo whilein cui si incrementano je kprima di fare l’assegnazione:

Versione finale.

b[0] = -1; b[1] = 0;

int k = 0; int j = 1;

while(j < m-1) {

while(k >= 0 && s[j] != s[k]) k = b[k];

b[++j] = ++k;

}

return b;

}

Esercizio: si scriva la versione analoga alla precedente in cui si inizializza fuori dal ciclo solo b[0]e non anche b[1].

Attenzione !

• La cosa più difficile da capire nell’algoritmo di KMP è l’istruzione k = b[k] del ciclo interno.

• Essa si basa sulla proprietà espressa dal Teorema 2.

• Nello studio, accertatevi di avere ben capito il ruolo di tale istruzione e del teorema, cioè di avere ben compreso che il istruzione e del teorema, cioè di avere ben compreso che il fatto che essa funzioni è una conseguenza del Teorema 2.

Analisi della complessità

• Si può dimostrare che l’algoritmo di preprocessing ha complessità O(m).

• L’algoritmo di ricerca, esclusa la fase di preprocessing, ha evidentemente complessità O(n).

• L’intero algoritmo di KMP ha quindi complessità O(m+n).

• Ma poiché è m ≤ n, la complessità è semplicemente O(n).

Abbi m quindi un l ritm lin r nziché qu dr tic

• Abbiamo quindi un algoritmo lineare anziché quadratico come l’algoritmo ingenuo.

Esempio di esecuzione dell’algoritmo di preprocess.

b[0] = -1; b[1] = 0

j = 1, k = 0: s[k] ≠ s[j] viene eseguito il corpo del while k = b[k]; ⇒ k = -1 non esiste bordo estendibile b[++j]= ++k; ⇒ b[2] = 0

pattern s: a b c a b c d

0 1 2 3 4 5 6 7 8

a b

j = 2, k = 0: s[k] ≠ s[j] viene eseguito il corpo del while k = b[k]; ⇒ k = -1 non esiste bordo estendibile b[++j]= ++k; ⇒ b[3] = 0

j = 3, k = 0: s[k] = s[j] non viene eseguito il corpo del while b[++j]= ++k; ⇒ b[4] = 1 (bordo estendibile) j = 4, k = 1: s[k] = s[j] non viene eseguito il corpo del while b[++j]= ++k; ⇒ b[5] = 2 (bordo estendibile)

Esempio.

j = 5, k = 2: s[k] = s[j] non viene eseguito il corpo del while b[++j]= ++k; ⇒ b[6] = 3 (bordo estendibile) j = 6, k = 3: s[k] ≠ s[j] si esegue il corpo del while k = b[k] = b[3] ⇒ k = 0

a b c a b c d

0 1 2 3 4 5 6 7 8

pattern s: a b

k = 0, s[k] ≠ s[j] si riesegue il corpo del while k = b[k]; ⇒ k = -1 non esiste bordo estendibile b[++j]= ++k; ⇒ b[7] = 0

j = 7, k = 0: s[k] = s[j] non viene eseguito il corpo del while b[++j]= ++k; ⇒ b[8] = 1 (bordo estendibile)

b: -1 0 0 0 1 2 3

0 1 2 3 4 5 6 7 8

0 1