Dat un text txt[0 . . . N-1] și un model pat[0 . . . M-1] , scrieți o funcție de căutare (char pat[], char txt[]) care afișează toate aparițiile lui pat[] în txt[]. Puteți presupune că N > M .

Exemple:

Intrare: txt[] = ACESTA ESTE UN TEXT DE TEST, pat[] = TEST
Ieșire: Model găsit la indexul 10

Intrare: txt[] = PĂRINȚI TĂI
pat[] = AABA
Ieșire: Model găsit la indexul 0, Model găsit la indexul 9, Model găsit la indexul 12

Sosiri de model în text

Am discutat despre algoritmul naiv de căutare a modelelor în postarea anterioară . Cel mai rău caz de complexitate a algoritmului Naive este O(m(n-m+1)). Complexitatea de timp a algoritmului KMP este O(n+m) în cel mai rău caz.

Căutare de modele KMP (Knuth Morris Pratt):

The Algoritm naiv de căutare a modelelor nu funcționează bine în cazurile în care vedem multe caractere care se potrivesc urmate de un caracter care nu se potrivește.

Exemple:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (nu este un caz cel mai rău, dar un caz prost pentru Naive)

Algoritmul de potrivire KMP folosește proprietatea degenerativă (modelul având aceleași sub-modeluri care apar de mai multe ori în model) a modelului și îmbunătățește complexitatea în cel mai rău caz la O(n+m) .

Ideea de bază din spatele algoritmului KMP este: ori de câte ori detectăm o nepotrivire (după unele potriviri), știm deja unele dintre caracterele din textul ferestrei următoare. Profităm de aceste informații pentru a evita potrivirea personajelor despre care știm că se vor potrivi oricum.

Prezentare generală a potrivirii

txt = AAAAABAAABA
pat = AAAA
Comparăm prima fereastră a TXT cu aceeași

txt = aaaa TATĂ
chiar = aaaa [Poziția inițială]
Găsim o potrivire. Aceasta este la fel ca Potrivirea șirurilor naive .

În pasul următor, comparăm următoarea fereastră de TXT cu aceeași .

txt = AAAAA DISTRUGE
chiar = aaaa [Modelul a fost deplasat cu o poziție]

Aici KMP face optimizarea peste Naive. În această a doua fereastră, comparăm doar al patrulea A al modelului
cu al patrulea caracter al ferestrei curente de text pentru a decide dacă fereastra curentă se potrivește sau nu. Din moment ce știm
primele trei caractere se vor potrivi oricum, am omis să se potrivească primele trei caractere.

Nevoie de preprocesare?

O întrebare importantă apare din explicația de mai sus, cum să știi câte caractere trebuie sărit. Ca sa stii asta,
preprocesăm modelul și pregătim un tablou întreg lps[] care ne spune numărul de caractere care trebuie sărit

Prezentare generală a preprocesării:

• Algoritmul KMP preprocesează pat[] și construiește un auxiliar lps[] de mărime m (la fel ca și dimensiunea modelului) care este folosit pentru a sări peste caractere în timpul potrivirii.
• Nume lps indică cel mai lung prefix propriu care este și un sufix. Un prefix adecvat este un prefix cu un șir întreg nu este permis. De exemplu, prefixele lui ABC sunt , A, AB și ABC. Prefixele adecvate sunt , A și AB. Sufixele șirului sunt , C, BC și ABC.
• Căutăm lps în submodele. Mai clar, ne concentrăm pe sub-șiruri de modele care sunt atât prefix, cât și sufix.
• Pentru fiecare sub-model pat[0..i] unde i = 0 la m-1, lps[i] stochează lungimea prefixului adecvat maxim care se potrivește, care este, de asemenea, un sufix al sub-modelului pat[0..i ].

lps[i] = cel mai lung prefix propriu al lui pat[0..i] care este, de asemenea, un sufix al lui pat[0..i].

Notă: lps[i] ar putea fi definit și ca cel mai lung prefix, care este și un sufix propriu. Trebuie să-l folosim corect într-un singur loc pentru a ne asigura că întregul subșir nu este luat în considerare.

Exemple de construcție lps[]:

Pentru modelul AAAA, lps[] este [0, 1, 2, 3]

Pentru modelul ABCDE, lps[] este [0, 0, 0, 0, 0]

Pentru modelul AABAACAABAA, lps[] este [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Pentru modelul AAAACAAAAAC, lps[] este [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Pentru modelul AAABAAA, lps[] este [0, 1, 2, 0, 1, 2, 3]

Algoritm de preprocesare:

În partea de preprocesare,

• Calculăm valori în lps[] . Pentru a face acest lucru, ținem evidența lungimii celei mai lungi valori de sufix de prefix (folosim numai variabilă în acest scop) pentru indicele anterior
• Inițializam lps[0] și numai ca 0.
• Dacă pat[len] și pat[i] potriviți, creștem numai cu 1 și atribuiți valoarea incrementată la lps[i].
• Dacă pat[i] și pat[len] nu se potrivesc și len nu este 0, actualizăm len la lps[len-1]
• Vedea computeLPSArray() în codul de mai jos pentru detalii

Ilustrație a preprocesării (sau construcției lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] este întotdeauna 0, trecem la i = 1

=> len = 0, i = 1:

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• stocați-l în lps[i] și faceți i++.
• Setați len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• stocați-l în lps[i] și faceți i++.
• Setați len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Deoarece pat[len] și pat[i] nu se potrivesc, iar len> 0,
• Setați len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Deoarece pat[len] și pat[i] nu se potrivesc și len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Deoarece pat[len] și pat[i] nu se potrivesc și len = 0,
• Setați lps[3] = 0 și i = 4

=> len = 0, i = 4:

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• Stocați-l în lps[i] și faceți i++.
• Setați len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

listbox java

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• Stocați-l în lps[i] și faceți i++.
• Setați len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• Stocați-l în lps[i] și faceți i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Deoarece pat[len] și pat[i] nu se potrivesc și len> 0,
• Setați len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Deoarece pat[len] și pat[i] se potrivesc, face len++,
• Stocați-l în lps[i] și faceți i++.
• len = 3, lps[7] = 3, i = 8

Ne oprim aici, deoarece am construit întregul lps[].

Implementarea algoritmului KMP:

spre deosebire de Algoritm naiv , unde glisăm modelul cu unul și comparăm toate caracterele la fiecare schimbare, folosim o valoare de la lps[] pentru a decide următoarele caractere care vor fi potrivite. Ideea este să nu se potrivească cu un personaj despre care știm că se va potrivi oricum.

Cum se utilizează lps[] pentru a decide următoarele poziții (sau pentru a ști numărul de caractere care trebuie sărit)?

• Începem compararea lui pat[j] cu j = 0 cu caracterele ferestrei curente de text.
• Continuăm să potrivim caracterele txt[i] și pat[j] și continuăm să incrementăm i și j în timp ce pat[j] și txt[i] păstrăm potrivire .
• Când vedem o nepotrivire
  • Știm că caracterele pat[0..j-1] se potrivesc cu txt[i-j…i-1] (Rețineți că j începe cu 0 și îl crește numai atunci când există o potrivire).
  • De asemenea, știm (din definiția de mai sus) că lps[j-1] este numărul de caractere ale pat[0...j-1] care sunt atât prefix și sufix propriu.
  • Din cele două puncte de mai sus, putem concluziona că nu trebuie să potrivim aceste caractere lps[j-1] cu txt[i-j…i-1] deoarece știm că aceste caractere se vor potrivi oricum. Să luăm în considerare exemplul de mai sus pentru a înțelege acest lucru.

Mai jos este ilustrarea algoritmului de mai sus:

Luați în considerare txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = aaaa

Dacă urmăm procesul de construire a LPS de mai sus, atunci lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] și pat[j] se potrivesc, do i++, j++

-> i = 1, j = 1: txt[i] și pat[j] se potrivesc, do i++, j++

-> i = 2, j = 2: txt[i] și pat[j] se potrivesc, do i++, j++

-> i = 3, j = 3: txt[i] și pat[j] se potrivesc, do i++, j++

-> i = 4, j = 4: Deoarece j = M, modelul de tipărire găsit și resetat j, j = lps[j-1] = lps[3] = 3

Aici, spre deosebire de algoritmul Naive, nu potrivim primele trei
personajele acestei ferestre. Valoarea lui lps[j-1] (în pasul de mai sus) ne-a oferit indexul următorului caracter de potrivire.

-> i = 4, j = 3: txt[i] și pat[j] se potrivesc, do i++, j++

-> i = 5, j = 4: Deoarece j == M, modelul de tipărire găsit și resetat j, j = lps[j-1] = lps[3] = 3
Din nou, spre deosebire de algoritmul Naive, nu potrivim primele trei caractere ale acestei ferestre. Valoarea lui lps[j-1] (în pasul de mai sus) ne-a oferit indexul următorului caracter de potrivire.

-> i = 5, j = 3: txt[i] și pat[j] NU se potrivesc și j> 0, schimbă doar j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] și pat[j] NU se potrivesc și j> 0, schimbă doar j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] și pat[j] NU se potrivesc și j> 0, schimbă doar j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] și pat[j] NU se potrivesc și j este 0, facem i++.

-> i = 6, j = 0: txt[i] și pat[j] se potrivesc, fac i++ și j++

-> i = 7, j = 1: txt[i] și pat[j] se potrivesc, fac i++ și j++

Continuăm în acest fel până când există suficiente caractere în text pentru a fi comparate cu caracterele din model...

Mai jos este implementarea abordării de mai sus:

C++

>

>

Java

str.inlocuire in java

>

>

Python3

>

>

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)) { dacă ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Model găsit la index '.($i - $j));  $j = $lps[$j - 1];  } // nepotrivire după ce j se potrivește altfel 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 ?>>>>
 
 
 
 
    
 
> 
    
 Found pattern at index 10>
 
    Complexitatea timpului:    O(N+M) unde N este lungimea textului și M este lungimea modelului care trebuie găsit.  
    Spațiu auxiliar:    O(M)