Dato un testo txt[0 . . . N-1] e uno schema letto[0 . . . M-1] , scrivere una funzione search(char pat[], char txt[]) che stampi tutte le occorrenze di pat[] in txt[]. Puoi presumerlo N >M .

Esempi:

Ingresso: txt[] = QUESTO È UN TESTO DI PROVA, pat[] = PROVA
Produzione: Modello trovato all'indice 10

Ingresso: txt[] = I TUOI PADRI
pat[] = AABA
Produzione: Modello trovato all'indice 0, Modello trovato all'indice 9, Modello trovato all'indice 12

Arrivi di pattern nel testo

Abbiamo discusso l'algoritmo di ricerca di pattern Naive nel file messaggio precedente . La complessità del caso peggiore dell'algoritmo Naive è O(m(n-m+1)). La complessità temporale dell'algoritmo KMP è O(n+m) nel caso peggiore.

Ricerca di modelli KMP (Knuth Morris Pratt):

IL Algoritmo di ricerca di pattern ingenuo non funziona bene nei casi in cui vediamo molti caratteri corrispondenti seguiti da un carattere non corrispondente.

Esempi:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (non è il caso peggiore, ma un caso negativo per Naive)

L'algoritmo di corrispondenza KMP utilizza la proprietà degenerante (modello con gli stessi sottomodelli che compaiono più di una volta nel modello) del modello e migliora la complessità del caso peggiore per O(n+m) .

L’idea di base dell’algoritmo di KMP è: ogni volta che rileviamo una mancata corrispondenza (dopo alcune corrispondenze), conosciamo già alcuni dei caratteri nel testo della finestra successiva. Approfittiamo di queste informazioni per evitare di abbinare i caratteri che sappiamo corrisponderanno comunque.

Panoramica delle corrispondenze

testo = AAAAABAAABA
pat = AAAA
Confrontiamo la prima finestra di TXT con lo stesso

txt= AAAA PADRE
anche = AAAA [Posizione iniziale]
Troviamo una corrispondenza. Questo è lo stesso di Corrispondenza di stringhe ingenua .

Nel passaggio successivo, confrontiamo la finestra successiva di TXT con lo stesso .

txt= AAAAA DISTRUGGERE
anche = AAAA [Il disegno si è spostato di una posizione]

È qui che KMP esegue l'ottimizzazione su Naive. In questa seconda finestra confrontiamo solo la quarta A del pattern
con il quarto carattere della finestra di testo corrente per decidere se la finestra corrente corrisponde o meno. Dato che lo sappiamo
i primi tre caratteri corrisponderanno comunque, abbiamo saltato la corrispondenza dei primi tre caratteri.

Necessità di preelaborazione?

il mio cricket dal vivo

Dalla spiegazione di cui sopra sorge una domanda importante: come sapere quanti caratteri devono essere saltati. Per sapere questo,
pre-elaboriamo il pattern e prepariamo un array di numeri interi lps[] che ci dice il conteggio dei caratteri da saltare

Panoramica della preelaborazione:

• L'algoritmo KMP preelabora pat[] e costruisce un ausiliario lps[] di dimensione M (uguale alla dimensione del modello) che viene utilizzato per saltare i caratteri durante la corrispondenza.
• Nome lps indica il prefisso proprio più lungo che è anche un suffisso. Un prefisso corretto è un prefisso con un'intera stringa non consentita. Ad esempio, i prefissi di ABC sono , A, AB e ABC. I prefissi corretti sono , A e AB. I suffissi della stringa sono , C, BC e ABC.
• Cerchiamo lps nei sottomodelli. Più chiaramente ci concentriamo su sottostringhe di modelli che sono sia prefisso che suffisso.
• Per ogni sottomodello pat[0..i] dove i = da 0 a m-1, lps[i] memorizza la lunghezza del prefisso proprio di corrispondenza massimo che è anche un suffisso del sottomodello pat[0..i ].

lps[i] = il prefisso proprio più lungo di pat[0..i] che è anche un suffisso di pat[0..i].

Nota: lps[i] potrebbe anche essere definito come il prefisso più lungo che è anche un suffisso proprio. Dobbiamo usarlo correttamente in un posto per assicurarci che l'intera sottostringa non venga considerata.

Esempi di costruzione lps[]:

Per il modello AAAA, lps[] è [0, 1, 2, 3]

Per il modello ABCDE, lps[] è [0, 0, 0, 0, 0]

Per il modello AABAACAAABAA, lps[] è [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Per il modello AAACAAAAAC, lps[] è [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Per il modello AAABAAA, lps[] è [0, 1, 2, 0, 1, 2, 3]

Algoritmo di preelaborazione:

Nella parte di preelaborazione,

• Calcoliamo i valori in lps[] . Per fare ciò, teniamo traccia della lunghezza del valore del suffisso del prefisso più lungo (usiamo soltanto variabile a questo scopo) per l'indice precedente
• Inizializziamo lps[0] E soltanto come 0.
• Se pat[len] E letti corrisponde, incrementiamo soltanto per 1 e assegnare il valore incrementato a lps[i].
• Se pat[i] e pat[len] non corrispondono e len non è 0, aggiorniamo len in lps[len-1]
• Vedere computaLPSArray() nel codice seguente per i dettagli

Illustrazione della preelaborazione (o costruzione di lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] è sempre 0, passiamo a i = 1

=> len = 0, i = 1:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• memorizzalo in lps[i] ed esegui i++.
• Imposta len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• memorizzalo in lps[i] ed esegui i++.
• Imposta len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Poiché pat[len] e pat[i] non corrispondono e len> 0,
• Imposta len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Poiché pat[len] e pat[i] non corrispondono e len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Poiché pat[len] e pat[i] non corrispondono e len = 0,
• Impostare lps[3] = 0 e i = 4

=> len = 0, i = 4:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• Memorizzalo in lps[i] ed esegui i++.
• Imposta len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• Memorizzalo in lps[i] ed esegui i++.
• Imposta len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• Memorizzalo in lps[i] ed esegui i++.
• len = 3, lps[6] = 3, i = 7

=> lente = 3, i = 7:

• Poiché pat[len] e pat[i] non corrispondono e len> 0,
• Imposta len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Poiché pat[len] e pat[i] corrispondono, esegui len++,
• Memorizzalo in lps[i] ed esegui i++.
• len = 3, lps[7] = 3, i = 8

Ci fermiamo qui poiché abbiamo costruito l'intero lp[].

Implementazione dell'algoritmo KMP:

non mi piace il Algoritmo ingenuo , dove facciamo scorrere il pattern di uno e confrontiamo tutti i caratteri a ogni turno, utilizziamo un valore di lps[] per decidere i successivi caratteri da abbinare. L'idea è di non abbinare un personaggio che sappiamo corrisponderà comunque.

Come usare lps[] per decidere le posizioni successive (o per conoscere il numero di caratteri da saltare)?

• Iniziamo il confronto di pat[j] con j = 0 con i caratteri della finestra di testo corrente.
• Continuiamo ad abbinare i caratteri txt[i] e pat[j] e continuiamo a incrementare i e j mentre pat[j] e txt[i] continuano corrispondenza .
• Quando vediamo a mancata corrispondenza
  • Sappiamo che i caratteri pat[0..j-1] corrispondono a txt[i-j…i-1] (nota che j inizia con 0 e lo incrementa solo quando c'è una corrispondenza).
  • Sappiamo anche (dalla definizione precedente) che lps[j-1] è il conteggio dei caratteri di pat[0…j-1] che sono sia prefisso che suffisso propri.
  • Dai due punti precedenti, possiamo concludere che non è necessario abbinare questi caratteri lps[j-1] con txt[i-j…i-1] perché sappiamo che questi caratteri corrisponderanno comunque. Consideriamo l'esempio sopra per capirlo.

Di seguito è riportata l'illustrazione dell'algoritmo di cui sopra:

Considera txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Se seguiamo il processo di costruzione LPS di cui sopra, allora lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] e pat[j] corrispondono, fai i++, j++

-> i = 1, j = 1: txt[i] e pat[j] corrispondono, fai i++, j++

-> i = 2, j = 2: txt[i] e pat[j] corrispondono, fai i++, j++

-> i = 3, j = 3: txt[i] e pat[j] corrispondono, fai i++, j++

-> i = 4, j = 4: Poiché j = M, stampa il modello trovato e ripristina j, J = lps[j-1] = lps[3] = 3

Qui, a differenza dell'algoritmo Naive, non abbiniamo i primi tre
caratteri di questa finestra. Il valore di lps[j-1] (nel passaggio precedente) ci ha fornito l'indice del carattere successivo da abbinare.

-> i = 4, j = 3: txt[i] e pat[j] corrispondono, fai i++, j++

-> i = 5, j = 4: Poiché j == M, stampa il modello trovato e ripristina j, J = lps[j-1] = lps[3] = 3
Ancora una volta, a differenza dell'algoritmo Naive, non facciamo corrispondere i primi tre caratteri di questa finestra. Il valore di lps[j-1] (nel passaggio precedente) ci ha fornito l'indice del carattere successivo da abbinare.

-> i = 5, j = 3: txt[i] e pat[j] NON corrispondono e j> 0, cambia solo j. J = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] e pat[j] NON corrispondono e j> 0, cambia solo j. J = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] e pat[j] NON corrispondono e j> 0, cambia solo j. J = lps[j-1] = lps[0] = 0

quali mesi sono q3

-> i = 5, j = 0: txt[i] e pat[j] NON corrispondono e j è 0, facciamo i++.

-> i = 6, j = 0: txt[i] e pat[j] corrispondono, fai i++ e j++

-> i = 7, j = 1: txt[i] e pat[j] corrispondono, fai i++ e j++

Continuiamo in questo modo finché non ci sono caratteri sufficienti nel testo per essere confrontati con i caratteri del modello...

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

>

>

Giava

>

>

Python3

>

stringa al carattere Java

>

C#

>

>

Javascript

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // PHP program for implementation of KMP pattern searching // algorithm // Prints occurrences of txt[] in pat[] function KMPSearch($pat, $txt) {  $M = strlen($pat);  $N = strlen($txt);  // create lps[] that will hold the longest prefix suffix  // values for pattern  $lps=array_fill(0,$M,0);  // Preprocess the pattern (calculate lps[] array)  computeLPSArray($pat, $M, $lps);  $i = 0; // index for txt[]  $j = 0; // index for pat[]  while (($N - $i)>= ($M - $j)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Modello trovato nell'indice '.($i - $j));  $j = $lps[$j - 1];  } // mancata corrispondenza dopo j corrisponde a else if ($i<$N && $pat[$j] != $txt[$i]) {  // Do not match lps[0..lps[j-1]] characters,  // they will match anyway  if ($j != 0)  $j = $lps[$j - 1];  else  $i = $i + 1;  }  } } // Fills lps[] for given pattern pat[0..M-1] function computeLPSArray($pat, $M, &$lps) {  // Length of the previous longest prefix suffix  $len = 0;  $lps[0] = 0; // lps[0] is always 0  // The loop calculates lps[i] for i = 1 to M-1  $i = 1;  while ($i <$M) {  if ($pat[$i] == $pat[$len]) {  $len++;  $lps[$i] = $len;  $i++;  }  else // (pat[i] != pat[len])  {  // This is tricky. Consider the example.  // AAACAAAA and i = 7. The idea is similar  // to search step.  if ($len != 0) {  $len = $lps[$len - 1];  // Also, note that we do not increment  // i here  }  else // if (len == 0)  {  $lps[$i] = 0;  $i++;  }  }  } } // Driver program to test above function  $txt = 'ABABDABACDABABCABAB';  $pat = 'ABABCABAB';  KMPSearch($pat, $txt);   // This code is contributed by chandan_jnu ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produzione  
 
Found pattern at index 10>
 
    Complessità temporale:    O(N+M) dove N è la lunghezza del testo e M è la lunghezza del modello da trovare.  
    Spazio ausiliario:    O(M)