Annettu teksti txt[0 . . . N-1] ja kuvio sänky[0 . . . M-1] , kirjoita funktiohaku (char pat[], char txt[]), joka tulostaa kaikki funktion pat[] esiintymät txt[]-tiedostoon. Voit olettaa sen N > M .

Esimerkkejä:

Syöte: txt[] = TÄMÄ ON TESTITEKSTI, pat[] = TESTI
Lähtö: Malli löytyy indeksistä 10

Syöte: txt[] = PÄIVÄMÄÄRÄSI
pat[] = AABA
Lähtö: Kuvio löytyy indeksistä 0, kuvio löytyy indeksistä 9, kuvio löytyy indeksistä 12

Kuvion saapumiset tekstissä

Olemme keskustelleet naiivista kuvionhakualgoritmista julkaisussa edellinen postaus . Naiivin algoritmin pahin kompleksisuus on O(m(n-m+1)). KMP-algoritmin aikamonimutkaisuus on O(n+m) pahimmassa tapauksessa.

KMP (Knuth Morris Pratt) mallihaku:

The Naiivi kuvion etsintäalgoritmi ei toimi hyvin tapauksissa, joissa näemme monia vastaavia merkkejä, joita seuraa yhteensopimaton merkki.

Esimerkkejä:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (ei huonoin tapaus, mutta huono tapaus Naivelle)

KMP-sovitusalgoritmi käyttää kuvion rappeuttavaa ominaisuutta (kuvio, jolla on samat alikuviot, jotka esiintyvät kuviossa useammin kuin kerran) ja parantaa pahimman tapauksen monimutkaisuutta. O(n+m) .

KMP:n algoritmin perusidea on: aina kun havaitsemme yhteensopimattomuuden (joidenkin osumien jälkeen), tiedämme jo osan seuraavan ikkunan tekstin merkeistä. Hyödynnämme näitä tietoja välttääksemme täsmäämästä merkkejä, joiden tiedämme vastaavan joka tapauksessa.

Vastaava yleiskatsaus

txt = AAAAABAAABA
pat = AAAA
Vertailemme ensimmäistä ikkunaa txt kanssa sama

txt = AAAA ISÄ
jopa = AAAA [Alkuperäinen sijainti]
Löydämme ottelun. Tämä on sama kuin Naiivi merkkijonojen sovitus .

Seuraavassa vaiheessa vertaamme seuraavaa ikkunaa txt kanssa sama .

txt = AAAAA TUHOTA
jopa = AAAA [Kuvio siirretty yksi paikka]

Tässä KMP tekee optimoinnin Naiven yli. Tässä toisessa ikkunassa vertaamme vain kuvion neljättä A:ta
nykyisen tekstiikkunan neljännellä merkillä päättääksesi, vastaako nykyinen ikkuna vai ei. Siitä lähtien kun tiedämme
kolme ensimmäistä merkkiä täsmäävät joka tapauksessa, jätimme kolmen ensimmäisen merkin vastaavuuden väliin.

Tarvitsetko esikäsittelyä?

Yllä olevasta selityksestä nousee tärkeä kysymys, kuinka tietää kuinka monta merkkiä ohitetaan. Tietääksesi tämän,
esikäsittelemme kuvion ja valmistelemme kokonaislukutaulukon lps[], joka kertoo ohitettavien merkkien määrän

Esikäsittelyn yleiskatsaus:

• KMP-algoritmi esikäsittelee pat[]:n ja muodostaa apuohjelman lps[] kooltaan m (sama kuin kuvion koko), jota käytetään merkkien ohittamiseen sovittaessa.
• Nimi lps osoittaa pisimmän oikean etuliitteen, joka on myös jälkiliite. Oikea etuliite on etuliite, jonka koko merkkijono ei ole sallittu. Esimerkiksi ABC:n etuliitteet ovat , A, AB ja ABC. Oikeat etuliitteet ovat , A ja AB. Merkkijonon jälkiliitteet ovat , C, BC ja ABC.
• Etsimme lps alikuvioissa. Selvemmin keskitymme kuvioiden osamerkkijonoihin, jotka ovat sekä etu- että jälkiliitteitä.
• Jokaiselle alikuvion kuvio[0..i], jossa i = 0 - m-1, lps[i] tallentaa suurimman vastaavan oikean etuliitteen pituuden, joka on myös alikuvion kuvion[0..i] pääte. ].

lps[i] = Pat[0..i]:n pisin oikea etuliite, joka on myös pat[0..i]:n pääte.

Huomautus: lps[i] voidaan myös määritellä pisimmäksi etuliitteeksi, joka on myös oikea pääte. Meidän on käytettävä sitä oikein yhdessä paikassa varmistaaksemme, että koko alimerkkijonoa ei oteta huomioon.

Esimerkkejä lps[]-rakenteesta:

Mallille AAAA lps[] on [0, 1, 2, 3]

Mallille ABCDE lps[] on [0, 0, 0, 0, 0]

Mallille AABAACAABAA lps[] on [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Mallille AAACAAAAAC lps[] on [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Mallille AAABAAA lps[] on [0, 1, 2, 0, 1, 2, 3]

Esikäsittelyalgoritmi:

Esikäsittelyosassa

• Laskemme arvot sisään lps[] . Tätä varten pidämme kirjaa pisimmän etuliitteen päätearvon pituudesta (käytämme vain muuttuja tätä tarkoitusta varten) edelliselle indeksille
• Alustamme lps[0] ja vain kuin 0.
• Jos pat[len] ja sängyt vastaa, lisäämme vain 1:llä ja anna lisätty arvo lps[i]:lle.
• Jos pat[i] ja pat[len] eivät täsmää ja len ei ole 0, päivitämme lenin lps[len-1]:ksi.
• Katso laske LSAarray() alla olevassa koodissa saadaksesi lisätietoja

Kuva esikäsittelystä (tai lps:n rakentamisesta[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] on aina 0, siirrymme kohtaan i = 1

=> len = 0, i = 1:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• tallenna se lps[i]:ään ja tee i++.
• Aseta len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• tallenna se lps[i]:ään ja tee i++.
• Aseta len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Koska pat[len] ja pat[i] eivät täsmää ja len> 0,
• Aseta len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Koska pat[len] ja pat[i] eivät täsmää ja len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Koska pat[len] ja pat[i] eivät täsmää ja len = 0,
• Aseta lps[3] = 0 ja i = 4

=> len = 0, i = 4:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• Tallenna se lps[i]:ään ja tee i++.
• Aseta len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• Tallenna se lps[i]:ään ja tee i++.
• Aseta len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• Tallenna se lps[i]:ään ja tee i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Koska pat[len] ja pat[i] eivät täsmää ja len> 0,
• Aseta len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Koska pat[len] ja pat[i] täsmäävät, tee len++,
• Tallenna se lps[i]:ään ja tee i++.
• len = 3, lps[7] = 3, i = 8

Pysähdymme tähän, kun olemme rakentaneet koko lps[].

KMP-algoritmin toteutus:

toisin kuin Naiivi algoritmi , jossa liu'utamme kuviota yhdellä ja vertaamme kaikkia merkkejä kussakin vuorossa, käytämme arvoa lps[]:stä päättääksemme seuraavat merkit. Ajatuksena on olla vastaamatta hahmoon, jonka tiedämme vastaavan joka tapauksessa.

Kuinka käyttää lps[]:tä seuraavien paikkojen päättämiseen (tai ohitettavien merkkien määrän selvittämiseen)?

• Aloitamme pat[j]:n vertailun arvolla j = 0 nykyisen tekstiikkunan merkeillä.
• Pidämme vastaavia merkkejä txt[i] ja pat[j] ja lisäämme i:tä ja j:tä samalla kun pat[j] ja txt[i] säilyvät yhteensopivuus .
• Kun näemme a epäsuhta
  • Tiedämme, että merkit pat[0..j-1] täsmäävät txt[i-j…i-1]:n kanssa (Huomaa, että j alkaa 0:lla ja lisää sitä vain, kun vastaavuus löytyy).
  • Tiedämme myös (yllä olevasta määritelmästä), että lps[j-1] on pat[0…j-1] merkkien määrä, jotka ovat sekä oikea etuliite että pääte.
  • Yllä olevista kahdesta kohdasta voimme päätellä, että meidän ei tarvitse sovittaa näitä lps[j-1]-merkkejä txt[i-j…i-1]:n kanssa, koska tiedämme, että nämä merkit täsmäävät joka tapauksessa. Tarkastellaanpa yllä olevaa esimerkkiä ymmärtääksemme tämän.

Alla on esimerkki yllä olevasta algoritmista:

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

Jos noudatamme yllä olevaa LPS-rakennusprosessia lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] ja pat[j] täsmäävät, tee i++, j++

-> i = 1, j = 1: txt[i] ja pat[j] täsmäävät, tee i++, j++

-> i = 2, j = 2: txt[i] ja pat[j] täsmäävät, tee i++, j++

-> i = 3, j = 3: txt[i] ja pat[j] täsmäävät, tee i++, j++

-> i = 4, j = 4: Koska j = M, tulostuskuvio löytyi ja nollaa j, j = lps[j-1] = lps[3] = 3

Tässä toisin kuin Naive-algoritmi, emme täsmää kolmea ensimmäistä
tämän ikkunan merkit. Arvo lps[j-1] (edellä olevassa vaiheessa) antoi meille seuraavan vastaavan merkin indeksin.

-> i = 4, j = 3: txt[i] ja pat[j] sopivat, tee i++, j++

-> i = 5, j = 4: Koska j == M, tulostuskuvio löytyi ja nollaa j, j = lps[j-1] = lps[3] = 3
Jälleen toisin kuin Naive-algoritmi, emme täsmää tämän ikkunan kolmea ensimmäistä merkkiä. Arvo lps[j-1] (edellä olevassa vaiheessa) antoi meille seuraavan vastaavan merkin indeksin.

-> i = 5, j = 3: txt[i] ja pat[j] EIVÄT täsmää ja j> 0, muuta vain j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] ja pat[j] EIVÄT täsmää ja j> 0, muuta vain j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] ja pat[j] EIVÄT täsmää ja j> 0, muuta vain j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] ja pat[j] EIVÄT täsmää ja j on 0, teemme i++.

-> i = 6, j = 0: txt[i] ja pat[j] sopivat, tee i++ ja j++

-> i = 7, j = 1: txt[i] ja pat[j] sopivat, tee i++ ja j++

Jatketaan näin, kunnes tekstissä on tarpeeksi merkkejä verrattavaksi kuvion merkkeihin…

Alla on yllä olevan lähestymistavan toteutus:

C++

>

>

Java

>

>

Python 3

sisältää merkkijonossa

>

>

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('Löytyi kuvio hakemistosta '.($i - $j));  $j = $lps[$j - 1];  } // epäsuhta j:n jälkeen vastaa 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>
 
    Aika monimutkaisuus:    O(N+M) missä N on tekstin pituus ja M on löydettävän kuvion pituus.  
    Aputila:    O(M)