Dots teksts txt[0 . . . N-1] un modelis gulta[0 . . . M-1] , ierakstiet funkciju Search (char pat[], char txt[]), kas izdrukā visus pat[] gadījumus txt[]. Jūs to varat pieņemt N > M .

Piemēri:

Ievade: txt[] = ŠIS IR PĀRBAUDES TEKSTS, pat[] = PĀRBAUDE
Izvade: Raksts atrasts indeksā 10

Ievade: txt[] = JŪSU DATUMS
pat[] = AABA
Izvade: Raksts atrasts indeksā 0, modelis atrasts indeksā 9, modelis atrasts indeksā 12

Raksta ienākšana tekstā

Mēs esam apsprieduši naivo modeļu meklēšanas algoritmu iepriekšējā ziņa . Naivā algoritma sliktākā gadījuma sarežģītība ir O(m(n-m+1)). KMP algoritma laika sarežģītība sliktākajā gadījumā ir O(n+m).

KMP (Knuts Morris Pratt) raksta meklēšana:

The Naivs modeļu meklēšanas algoritms nedarbojas labi gadījumos, kad redzam daudzas atbilstošas ​​rakstzīmes, kurām seko neatbilstošs rakstzīmes.

Piemēri:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (nav sliktākais gadījums, bet slikts gadījums)

KMP atbilstības algoritms izmanto modeļa deģenerējošu īpašību (modelis ar vienādiem apakšrakstiem, kas parādās vairāk nekā vienu reizi) paraugā un uzlabo sliktākā gadījuma sarežģītību, lai O(n+m) .

KMP algoritma pamatideja ir: ikreiz, kad mēs atklājam neatbilstību (pēc dažām atbilstībām), mēs jau zinām dažas rakstzīmes nākamā loga tekstā. Mēs izmantojam šo informāciju, lai izvairītos no to rakstzīmju sakritības, kuras, kā zināms, sakritīs.

Atbilstošs pārskats

txt = AAAAABAAABA
pat = AAAA
Mēs salīdzinām pirmo logu txt ar tas pats

txt = AAAA TĒVS
pat = AAAA [Sākotnējā pozīcija]
Mēs atrodam atbilstību. Šis ir tāds pats kā Naiva stīgu saskaņošana .

Nākamajā darbībā mēs salīdzinām nākamo logu txt ar tas pats .

txt = AAAAA IZNĪCINĀT
pat = AAAA [Raksts nobīdīts par vienu pozīciju]

Šeit KMP veic optimizāciju, nevis Naive. Šajā otrajā logā mēs salīdzinām tikai ceturto A modeļa
ar pašreizējā teksta loga ceturto rakstzīmi, lai izlemtu, vai pašreizējais logs atbilst vai nē. Kopš mēs zinām
pirmās trīs rakstzīmes tik un tā sakritīs, mēs izlaidām pirmo trīs rakstzīmju atbilstību.

Nepieciešama pirmapstrāde?

No iepriekš minētā skaidrojuma rodas svarīgs jautājums, kā uzzināt, cik rakstzīmju ir jāizlaiž. Lai to zinātu,
mēs iepriekš apstrādājam modeli un sagatavojam veselu skaitļu masīvu lps[], kas norāda izlaižamo rakstzīmju skaitu

Priekšapstrādes pārskats:

• KMP algoritms iepriekš apstrādā pat[] un konstruē palīgprogrammu lps[] izmēra m (tāds pats kā raksta izmērs), ko izmanto, lai izlaistu rakstzīmes atbilstības noteikšanas laikā.
• Vārds lps norāda garāko pareizo prefiksu, kas ir arī sufikss. Pareizs prefikss ir prefikss, kurā nav atļauta vesela virkne. Piemēram, ABC prefiksi ir , A, AB un ABC. Pareizie prefiksi ir , A un AB. Virknes sufiksi ir , C, BC un ABC.
• Mēs meklējam lps apakšmodeļos. Skaidrāk mēs koncentrējamies uz rakstu apakšvirknēm, kurām ir gan prefikss, gan sufikss.
• Katram apakšmotera modelim[0..i], kur i = 0 līdz m-1, lps[i] saglabā maksimālā atbilstošā pareizā prefiksa garumu, kas ir arī apakšmota modeļa[0..i] sufikss. ].

lps[i] = pat[0..i] garākais pareizais prefikss, kas ir arī pat[0..i] sufikss.

Piezīme: lps[i] var definēt arī kā garāko prefiksu, kas ir arī atbilstošs sufikss. Mums tas ir pareizi jāizmanto vienā vietā, lai pārliecinātos, ka netiek ņemta vērā visa apakšvirkne.

Lps[] konstrukcijas piemēri:

Paraugam AAAA lps[] ir [0, 1, 2, 3]

Modelim ABCDE lps[] ir [0, 0, 0, 0, 0]

Paraugam AABAACAABAA lps[] ir [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Paraugam AAACAAAAAC lps[] ir [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Paraugam AAABAAA lps[] ir [0, 1, 2, 0, 1, 2, 3]

Priekšapstrādes algoritms:

Priekšapstrādes daļā

• Mēs aprēķinām vērtības lps[] . Lai to izdarītu, mēs sekojam līdzi garākā prefiksa sufiksa vērtības garumam (mēs izmantojam tikai mainīgais šim nolūkam) iepriekšējam indeksam
• Mēs inicializējam lps[0] un tikai kā 0.
• Ja pat[len] un gultas sakrīt, mēs palielinām tikai ar 1 un piešķiriet palielināto vērtību lps[i].
• Ja pat[i] un pat[len] nesakrīt un len nav 0, mēs atjauninām len uz lps[len-1]
• Skat aprēķināt LSAarray() zemāk esošajā kodā, lai iegūtu sīkāku informāciju

Priekšapstrādes (vai lps [] uzbūves) ilustrācija:

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] vienmēr ir 0, mēs pārejam uz i = 1

=> len = 0, i = 1:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• saglabājiet to lps[i] un veiciet i++.
• Iestatiet len ​​= 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• saglabājiet to lps[i] un veiciet i++.
• Iestatiet len ​​= 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Tā kā pat[len] un pat[i] nesakrīt un len> 0,
• Iestatiet len ​​= lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Tā kā pat[len] un pat[i] nesakrīt un len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Tā kā pat[len] un pat[i] nesakrīt un len = 0,
• Iestatiet lps[3] = 0 un i = 4

=> len = 0, i = 4:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• Saglabājiet to lps[i] un veiciet i++.
• Iestatiet len ​​= 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• Saglabājiet to lps[i] un veiciet i++.
• Iestatiet len ​​= 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• Saglabājiet to lps[i] un veiciet i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Tā kā pat[len] un pat[i] nesakrīt un len> 0,
• Iestatiet len ​​= lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Tā kā pat[len] un pat[i] atbilst, izmantojiet len++,
• Saglabājiet to lps[i] un veiciet i++.
• len = 3, lps[7] = 3, i = 8

Šeit mēs apstājamies, jo esam izveidojuši visu lps[].

KMP algoritma ieviešana:

Atšķirībā no Naivs algoritms , kur mēs slīdām paraugu par vienu un salīdzinām visas rakstzīmes katrā maiņā, mēs izmantojam vērtību no lps[], lai izlemtu, kādas rakstzīmes ir jāsaskaņo. Ideja ir nesaskaņot raksturu, par kuru mēs zinām, ka tas tik un tā atbilst.

Kā izmantot lps[], lai izlemtu nākamās pozīcijas (vai uzzinātu izlaižamo rakstzīmju skaitu)?

• Pat[j] salīdzināšanu ar j = 0 sākam ar pašreizējā teksta loga rakstzīmēm.
• Mēs turpinām saskaņot rakstzīmes txt[i] un pat[j] un turpinām palielināt i un j, kamēr pat[j] un txt[i] saglabājam saskaņošana .
• Kad mēs redzam a neatbilstība
  • Mēs zinām, ka rakstzīmes pat[0..j-1] sakrīt ar txt[i-j…i-1] (Ņemiet vērā, ka j sākas ar 0 un palielina to tikai tad, ja ir atbilstība).
  • Mēs arī zinām (no iepriekš minētās definīcijas), ka lps[j-1] ir pat[0…j-1] rakstzīmju skaits, kas ir gan pareizais prefikss, gan sufikss.
  • No iepriekšminētajiem diviem punktiem mēs varam secināt, ka mums nav jāsaskaņo šīs lps[j-1] rakstzīmes ar txt[i-j…i-1], jo mēs zinām, ka šīs rakstzīmes tik un tā sakritīs. Apskatīsim iepriekš minēto piemēru, lai to saprastu.

Tālāk ir parādīts iepriekšminētā algoritma ilustrācija:

Apsveriet txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Ja sekojam augstāk minētajam LPS veidošanas procesam tad lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] un pat[j] sakrīt, veiciet i++, j++

-> i = 1, j = 1: txt[i] un pat[j] sakrīt, veiciet i++, j++

-> i = 2, j = 2: txt[i] un pat[j] sakrīt, veiciet i++, j++

-> i = 3, j = 3: txt[i] un pat[j] sakrīt, veiciet i++, j++

-> i = 4, j = 4: Tā kā j = M, tika atrasts drukas raksts un atiestatīts j, j = lps[j-1] = lps[3] = 3

Šeit atšķirībā no naivā algoritma mēs neatbilstam pirmajiem trim
šī loga rakstzīmes. Lps[j-1] vērtība (iepriekšējā solī) deva mums nākamās atbilstības rakstzīmes indeksu.

-> i = 4, j = 3: txt[i] un pat[j] sakrīt, veiciet i++, j++

-> i = 5, j = 4: Tā kā j == M, drukas raksts atrasts un atiestatīts j, j = lps[j-1] = lps[3] = 3
Atkal atšķirībā no Naive algoritma mēs nesakrītam šī loga pirmās trīs rakstzīmes. Lps[j-1] vērtība (iepriekšējā solī) deva mums nākamās atbilstības rakstzīmes indeksu.

-> i = 5, j = 3: txt[i] un pat[j] NEatbilst un j> 0, mainiet tikai j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] un pat[j] NEatbilst un j> 0, mainiet tikai j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] un pat[j] NEatbilst un j> 0, mainiet tikai j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] un pat[j] NAV sakrīt, un j ir 0, mēs darām i++.

-> i = 6, j = 0: txt[i] un pat[j] sakrīt, veiciet i++ un j++

-> i = 7, j = 1: txt[i] un pat[j] sakrīt, veiciet i++ un j++

Mēs turpinām šo ceļu, līdz tekstā ir pietiekami daudz rakstzīmju, lai tos salīdzinātu ar rakstzīmēm...

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

C++

>

>

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)) { if ($pat[$j] == $txt[$i]) { $j++;  $i++;  } if ($j == $M) { printf('Atrasts raksts indeksā '.($i - $j));  $j = $lps[$j - 1];  } // neatbilstība pēc j atbilst 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 ?>>>
 
 
 
 
    
policijas komisāra asistents
 
> 
    
 Found pattern at index 10>
 
    Laika sarežģītība:    O(N+M), kur N ir teksta garums un M ir jāatrod parauga garums.  
    Palīgtelpa:    O(M)