Duotas tekstas txt[0 . . . N-1] ir modelis lova[0 . . . M-1] , parašykite paieškos funkciją (char pat[], char txt[]), kuri spausdina visus pat[] atvejus txt[]. Galite manyti, kad N > M .

Pavyzdžiai:

Įvestis: txt[] = TAI BANDYMAS TEKSTAS, pat[] = TESTAS
Išvestis: Raštas rastas 10 indekse

Įvestis: txt[] = JŪSŲ TĖVAI
pat[] = AABA
Išvestis: Šablonas rastas indeksu 0, modelis rastas indeksu 9, modelis rastas indeksu 12

Rašto atsiradimas tekste

Mes aptarėme naivų modelių paieškos algoritmą ankstesnis įrašas . Blogiausias naivaus algoritmo sudėtingumas yra O(m(n-m+1)). KMP algoritmo laiko sudėtingumas blogiausiu atveju yra O(n+m).

KMP (Knuth Morris Pratt) šablono paieška:

The Naivus modelio paieškos algoritmas neveikia tais atvejais, kai matome daug sutampančių simbolių, po kurių seka nesutampantis simbolis.

Pavyzdžiai:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (ne blogiausias atvejis, bet blogas atvejis Naive)

mašinraščio jungiklis

KMP atitikimo algoritmas naudoja degeneruojančią modelio savybę (šablonas, turintis tuos pačius antrinius šablonus, kurie šablone atsiranda daugiau nei vieną kartą) ir pagerina blogiausio atvejo sudėtingumą. O(n+m) .

Pagrindinė KMP algoritmo idėja yra tokia: kai tik nustatome neatitikimą (po kai kurių atitikčių), mes jau žinome kai kuriuos kito lango teksto simbolius. Naudojamės šia informacija, kad nesutaptume simbolių, kurie, kaip žinome, vis tiek atitiks.

Atitikimo apžvalga

txt = AAAAABAAABA
pat = AAAA
Mes lyginame pirmąjį langą txt su pat

txt = AAAA TĖVAS
pat = AAAA [Pradinė padėtis]
Mes randame atitikmenį. Tai tas pats kaip Naivus stygų atitikimas .

Kitame veiksme palyginame kitą langą txt su pat .

txt = AAAAA NAIKINTI
pat = AAAA [Šablonas pasislinkęs viena padėtimi]

Čia KMP atlieka optimizavimą, o ne Naive. Šiame antrame lange lyginame tik ketvirtąjį modelio A
su ketvirtuoju dabartinio teksto lango simboliu, kad nuspręstumėte, ar dabartinis langas atitinka, ar ne. Kadangi žinome
pirmieji trys simboliai vis tiek atitiks, mes praleidome pirmųjų trijų simbolių atitikimą.

Reikia išankstinio apdorojimo?

Iš aukščiau pateikto paaiškinimo kyla svarbus klausimas, kaip žinoti, kiek simbolių reikia praleisti. Norėdami tai žinoti,
iš anksto apdorojame šabloną ir paruošiame sveikųjų skaičių masyvą lps[], kuris nurodo praleistinų simbolių skaičių

Išankstinio apdorojimo apžvalga:

• KMP algoritmas iš anksto apdoroja pat[] ir sukuria pagalbinį elementą lps[] dydžio m (toks pat kaip rašto dydis), kuris naudojamas simboliams praleisti derinant.
• vardas lps nurodo ilgiausią tinkamą priešdėlį, kuris kartu yra ir priesaga. Tinkamas priešdėlis yra priešdėlis, kurio visa eilutė neleidžiama. Pavyzdžiui, ABC priešdėliai yra , A, AB ir ABC. Tinkami priešdėliai yra , A ir AB. Eilutės galūnės yra , C, BC ir ABC.
• Lps ieškome pogrupiuose. Aiškiau mes sutelkiame dėmesį į šablonų eilutes, kurios yra ir priešdėlis, ir priesagas.
• Kiekvienam pogrupio šablonui[0..i], kur i = 0 iki m-1, lps[i] išsaugo maksimalaus atitikimo tinkamo priešdėlio ilgį, kuris taip pat yra papildomo šablono [0..i] priesaga. ].

lps[i] = ilgiausias tinkamas pat[0..i] priešdėlis, kuris taip pat yra pat[0..i] priesaga.

Pastaba: lps [i] taip pat gali būti apibrėžtas kaip ilgiausias priešdėlis, kuris taip pat yra tinkama priesaga. Turime jį tinkamai naudoti vienoje vietoje, kad įsitikintume, jog neatsižvelgiama į visą eilutę.

Lps[] konstrukcijos pavyzdžiai:

Šablono AAAA atveju lps[] yra [0, 1, 2, 3]

Šablono ABCDE atveju lps[] yra [0, 0, 0, 0, 0]

Šablono AABAACAABAA atveju lps[] yra [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Šablono AAACAAAAAC atveju lps[] yra [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Šablono AAABAAA atveju lps[] yra [0, 1, 2, 0, 1, 2, 3]

Išankstinio apdorojimo algoritmas:

Išankstinio apdorojimo dalyje

• Mes apskaičiuojame reikšmes lps[] . Norėdami tai padaryti, stebime ilgiausio priešdėlio priesagos reikšmės ilgį (naudojame tik kintamasis šiam tikslui) ankstesniam indeksui
• Mes inicijuojame lps[0] ir tik kaip 0.
• Jeigu pat[len] ir lovos atitinka, mes padidiname tik 1 ir priskirkite padidintą reikšmę lps[i].
• Jei pat[i] ir pat[len] nesutampa ir len nėra 0, atnaujiname len į lps[len-1]
• Matyti apskaičiuotiLPSArray() žemiau esančiame kode, kad gautumėte daugiau informacijos

Išankstinio apdorojimo (arba lps [] konstravimo) iliustracija:

pat[] = AAAAAAA

=> len = 0, i = 0:

mylivecricket alternatyva

• lps[0] visada yra 0, pereiname prie i = 1

=> len = 0, i = 1:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• išsaugokite jį lps[i] ir atlikite i++.
• Nustatykite len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• išsaugokite jį lps[i] ir atlikite i++.
• Nustatykite len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Kadangi pat[len] ir pat[i] nesutampa, o len> 0,
• Nustatykite len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Kadangi pat[len] ir pat[i] nesutampa ir len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Kadangi pat[len] ir pat[i] nesutampa ir len = 0,
• Nustatykite lps[3] = 0 ir i = 4

=> len = 0, i = 4:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• Išsaugokite jį lps[i] ir atlikite i++.
• Nustatykite len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• Išsaugokite jį lps[i] ir atlikite i++.
• Nustatykite len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• Išsaugokite jį lps[i] ir atlikite i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Kadangi pat[len] ir pat[i] nesutampa ir len> 0,
• Nustatykite len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Kadangi pat[len] ir pat[i] sutampa, atlikite len++,
• Išsaugokite jį lps[i] ir atlikite i++.
• len = 3, lps[7] = 3, i = 8

Sustojame čia, nes sukonstravome visą lps[].

KMP algoritmo įgyvendinimas:

Skirtingai nuo Naivus algoritmas , kur slenkame šabloną po vieną ir lyginame visus simbolius kiekvienoje pamainoje, naudojame reikšmę iš lps[], kad nuspręstume, kuriuos simbolius reikia suderinti. Idėja yra nesutapti su charakteriu, kuris, kaip žinome, vis tiek atitiks.

Kaip naudoti lps[], norint nuspręsti dėl tolimesnių pozicijų (arba sužinoti, kiek simbolių reikia praleisti)?

• Pat[j] palyginimą su j = 0 pradedame dabartinio teksto lango simboliais.
• Mes nuolat deriname simbolius txt[i] ir pat[j] ir nuolat didiname i ir j, kol pat[j] ir txt[i] išlieka atitikimo .
• Kai matome a neatitikimas
  • Žinome, kad simboliai pat[0..j-1] sutampa su txt[i-j…i-1] (atminkite, kad j prasideda 0 ir padidina jį tik tada, kai yra atitiktis).
  • Taip pat žinome (iš anksčiau pateikto apibrėžimo), kad lps[j-1] yra pat[0…j-1] simbolių, kurie yra tinkamas priešdėlis ir priesaga, skaičius.
  • Iš aukščiau pateiktų dviejų punktų galime daryti išvadą, kad mums nereikia derinti šių lps[j-1] simbolių su txt[i-j…i-1], nes žinome, kad šie simboliai vis tiek sutaps. Norėdami tai suprasti, panagrinėkime aukščiau pateiktą pavyzdį.

Žemiau yra aukščiau pateikto algoritmo iliustracija:

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

Jei laikysimės aukščiau pateikto LPS kūrimo proceso, tada lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] ir pat[j] sutampa, darykite i++, j++

-> i = 1, j = 1: txt[i] ir pat[j] sutampa, darykite i++, j++

-> i = 2, j = 2: txt[i] ir pat[j] sutampa, darykite i++, j++

-> i = 3, j = 3: txt[i] ir pat[j] sutampa, darykite i++, j++

-> i = 4, j = 4: Kadangi j = M, rastas spausdinimo raštas ir iš naujo nustatomas j, j = lps[j-1] = lps[3] = 3

mylivecriclet

Čia, skirtingai nei naivus algoritmas, mes nesutampame pirmųjų trijų
šio lango simboliai. Lps [j-1] reikšmė (ankstesniame žingsnyje) suteikė mums kito atitikimo simbolio indeksą.

-> i = 4, j = 3: txt[i] ir pat[j] sutampa, darykite i++, j++

-> i = 5, j = 4: Kadangi j == M, rastas spausdinimo raštas ir iš naujo nustatytas j, j = lps[j-1] = lps[3] = 3
Vėlgi, skirtingai nei naivusis algoritmas, mes nesutampame pirmųjų trijų šio lango simbolių. Lps [j-1] reikšmė (ankstesniame žingsnyje) suteikė mums kito atitikimo simbolio indeksą.

-> i = 5, j = 3: txt[i] ir pat[j] nesutampa ir j> 0, pakeiskite tik j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] ir pat[j] nesutampa ir j> 0, pakeiskite tik j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] ir pat[j] nesutampa ir j> 0, pakeiskite tik j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] ir pat[j] NESUTAPA, o j yra 0, mes darome i++.

-> i = 6, j = 0: txt[i] ir pat[j] sutampa, darykite i++ ir j++

-> i = 7, j = 1: txt[i] ir pat[j] sutampa, darykite i++ ir j++

Taip tęsiame tol, kol tekste bus pakankamai simbolių, kad juos būtų galima palyginti su rašto simboliais...

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

C++

>

>

Java

>

>

krūva ir krūva rūšiuoti

Python3

>

>

C#

>

>

Javascript

> 
    
palyginti eilutėje
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
  // 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('Rastas šablonas indekse '.($i - $j));  $j = $lps[$j - 1];  } // neatitikimas po j atitinka 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 ?>>>
 
 
 
 
    
 
> 
    
 Found pattern at index 10>
 
    Laiko sudėtingumas:    O(N+M), kur N yra teksto ilgis, o M yra rašto, kurį reikia rasti, ilgis.  
    Pagalbinė erdvė:    O(M)