Givet en text txt[0 . . . N-1] och ett mönster säng[0 . . . M-1] , skriv en funktionssökning(char pat[], char txt[]) som skriver ut alla förekomster av pat[] i txt[]. Du kan anta det N > M .

Exempel:

Inmatning: txt[] = DETTA ÄR EN TESTTEXT, pat[] = TEST
Produktion: Mönster hittat i index 10

Inmatning: txt[] = DINA FÄDER
pat[] = AABA
Produktion: Mönster hittat vid index 0, Mönster hittades vid index 9, Mönster hittades vid index 12

Ankomster av mönster i texten

Vi har diskuterat den naiva mönstersökningsalgoritmen i tidigare inlägg . Det värsta fallet för den naiva algoritmen är O(m(n-m+1)). Tidskomplexiteten för KMP-algoritmen är O(n+m) i värsta fall.

KMP (Knuth Morris Pratt) mönstersökning:

De Naiv mönstersökningsalgoritm fungerar inte bra i fall där vi ser många matchande tecken följt av ett felmatchande tecken.

Exempel:

1) txt[] = AAAAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (inte ett värsta fall, men ett dåligt fall för naiv)

KMP-matchningsalgoritmen använder degenererande egenskap (mönster som har samma delmönster som förekommer mer än en gång i mönstret) för mönstret och förbättrar den värsta tänkbara komplexiteten för att O(n+m) .

Grundidén bakom KMP:s algoritm är: när vi upptäcker en missmatchning (efter några matchningar) känner vi redan till några av tecknen i texten i nästa fönster. Vi utnyttjar denna information för att undvika att matcha de karaktärer som vi vet ändå kommer att matcha.

Matchningsöversikt

txt = AAAAABAAABA
pat = AAAA
Vi jämför första fönstret av Text med det samma

txt = AAAA FAR
jämnt = AAAA [Första position]
Vi hittar en match. Detta är samma som Naiv strängmatchning .

I nästa steg jämför vi nästa fönster av Text med det samma .

txt = AAAAA FÖRSTÖRA
jämnt = AAAA [Mönstret flyttade en position]

Det är här KMP gör optimering över Naive. I detta andra fönster jämför vi bara det fjärde A av mönstret
med fjärde tecknet i aktuellt textfönster för att avgöra om det aktuella fönstret matchar eller inte. Eftersom vi vet
de tre första tecknen kommer ändå att matcha, vi hoppade över att matcha de tre första tecknen.

Behov av förbearbetning?

En viktig fråga uppstår från ovanstående förklaring, hur man vet hur många tecken som ska hoppa över. Att veta detta,
vi förbearbetar mönstret och förbereder en heltalsmatris lps[] som talar om för oss hur många tecken som ska hoppas över

partiell differentiering i latex

Förbearbetningsöversikt:

• KMP-algoritmen förbearbetar pat[] och konstruerar en hjälpenhet lps[] av storlek m (samma som storleken på mönstret) som används för att hoppa över tecken under matchning.
• namn lps indikerar det längsta riktiga prefixet som också är ett suffix. Ett korrekt prefix är ett prefix med en hel sträng som inte är tillåten. Till exempel är prefix för ABC , A, AB och ABC. Korrekt prefix är , A och AB. Suffixen för strängen är , C, BC och ABC.
• Vi söker efter lps i delmönster. Tydligare fokuserar vi på delsträngar av mönster som är både prefix och suffix.
• För varje sub-pattern pat[0..i] där i = 0 till m-1, lagrar lps[i] längden på det maximala matchande korrekta prefixet som också är ett suffix till sub-pattern pat[0..i] ].

lps[i] = det längsta riktiga prefixet för pat[0..i] som också är ett suffix till pat[0..i].

Notera: lps[i] kan också definieras som det längsta prefixet som också är ett korrekt suffix. Vi måste använda den ordentligt på ett ställe för att se till att hela delsträngen inte beaktas.

Exempel på lps[]-konstruktion:

För mönstret AAAA är lps[] [0, 1, 2, 3]

För mönstret ABCDE är lps[] [0, 0, 0, 0, 0]

För mönstret AABAACAABAA är lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

För mönstret AAACAAAAAC är lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

alya manasa

För mönstret AAABAAA är lps[] [0, 1, 2, 0, 1, 2, 3]

Förbearbetningsalgoritm:

I förbearbetningsdelen,

• Vi beräknar värden i lps[] . För att göra det håller vi reda på längden på det längsta prefixsuffixvärdet (vi använder endast variabel för detta ändamål) för föregående index
• Vi initierar lps[0] och endast som 0.
• Om pat[len] och sängar matchar, vi ökar endast med 1 och tilldela det ökade värdet till lps[i].
• Om pat[i] och pat[len] inte matchar och len inte är 0, uppdaterar vi len till lps[len-1]
• Ser computeLPSArray() i koden nedan för detaljer

Illustration av förbearbetning (eller konstruktion av lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

• lps[0] är alltid 0, vi flyttar till i = 1

=> len = 0, i = 1:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• lagra det i lps[i] och gör i++.
• Ställ in len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• lagra det i lps[i] och gör i++.
• Ställ in len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Eftersom pat[len] och pat[i] inte matchar, och len> 0,
• Ställ in len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Eftersom pat[len] och pat[i] inte matchar och len> 0,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Eftersom pat[len] och pat[i] inte matchar och len = 0,
• Ställ in lps[3] = 0 och i = 4

=> len = 0, i = 4:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• Lagra det i lps[i] och gör i++.
• Ställ in len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• Lagra det i lps[i] och gör i++.
• Ställ in len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• Lagra det i lps[i] och gör i++.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Eftersom pat[len] och pat[i] inte matchar och len> 0,
• Ställ in len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Eftersom pat[len] och pat[i] matchar, gör len++,
• Lagra det i lps[i] och gör i++.
• len = 3, lps[7] = 3, i = 8

Vi stannar här eftersom vi har konstruerat hela lps[].

Implementering av KMP-algoritm:

till skillnad från Naiv algoritm , där vi skjuter mönstret med ett och jämför alla tecken vid varje skift, använder vi ett värde från lps[] för att bestämma nästa tecken som ska matchas. Tanken är att inte matcha en karaktär som vi vet ändå kommer att matcha.

Hur använder man lps[] för att bestämma nästa positioner (eller för att veta hur många tecken som ska hoppas över)?

• Vi börjar jämförelsen av pat[j] med j = 0 med tecken i det aktuella textfönstret.
• Vi fortsätter att matcha tecknen txt[i] och pat[j] och fortsätter att öka i och j medan pat[j] och txt[i] behåller motsvarande .
• När vi ser en missanpassning
  • Vi vet att tecknen pat[0..j-1] matchar txt[i-j…i-1] (Observera att j börjar med 0 och ökar den bara när det finns en matchning).
  • Vi vet också (från ovanstående definition) att lps[j-1] är antalet tecken i pat[0...j-1] som är både korrekt prefix och suffix.
  • Från ovanstående två punkter kan vi dra slutsatsen att vi inte behöver matcha dessa lps[j-1]-tecken med txt[i-j...i-1] eftersom vi vet att dessa tecken ändå kommer att matcha. Låt oss överväga exemplet ovan för att förstå detta.

Nedan är illustrationen av ovanstående algoritm:

Överväg txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , klapp[] = AAAA

Om vi ​​följer ovanstående LPS byggprocess då lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] och pat[j] matchar, gör i++, j++

-> i = 1, j = 1: txt[i] och pat[j] matchar, gör i++, j++

-> i = 2, j = 2: txt[i] och pat[j] matchar, gör i++, j++

-> i = 3, j = 3: txt[i] och pat[j] matchar, gör i++, j++

-> i = 4, j = 4: Eftersom j = M, hittade skrivmönster och återställ j, j = lps[j-1] = lps[3] = 3

Här till skillnad från naiv algoritm matchar vi inte de tre första
tecken i detta fönster. Värdet på lps[j-1] (i steget ovan) gav oss index för nästa tecken att matcha.

-> i = 4, j = 3: txt[i] och pat[j] matchar, gör i++, j++

-> i = 5, j = 4: Eftersom j == M, skriv ut mönster hittat och återställ j, j = lps[j-1] = lps[3] = 3
Återigen till skillnad från naiv algoritm, matchar vi inte de tre första tecknen i det här fönstret. Värdet på lps[j-1] (i steget ovan) gav oss index för nästa tecken att matcha.

-> i = 5, j = 3: txt[i] och pat[j] matchar INTE och j> 0, ändra endast j. j = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] och pat[j] matchar INTE och j> 0, ändra endast j. j = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] och pat[j] matchar INTE och j> 0, ändra endast j. j = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] och pat[j] matchar INTE och j är 0, vi gör i++.

-> i = 6, j = 0: txt[i] och pat[j] matchar, gör i++ och j++

-> i = 7, j = 1: txt[i] och pat[j] matchar, gör i++ och j++

Vi fortsätter på detta sätt tills det finns tillräckligt många tecken i texten för att jämföras med tecknen i mönstret...

java boolesk

Nedan är implementeringen av ovanstående tillvägagångssätt:

C++

>

>

Java

java webbtjänster

>

>

Python3

>

>

C#

>

>

Javascript

> 
    
   
 
     
  
 
    
 
     
     
    
jämförbar sträng i java
 
 
 
 
 
  // 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('Hittade mönster vid index '.($i - $j));  $j = $lps[$j - 1];  } // missmatch efter j matchar annat 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 ?>>
 
 
 
 
    
 
>
 
    
 
>
 
  Produktion  
 
Found pattern at index 10>
 
    Tidskomplexitet:    O(N+M) där N är längden på texten och M är längden på mönstret som ska hittas.  
    Hjälputrymme:    O(M)