algorithm
Knuth Morris Pratt (KMP) algoritm
Sök…
Introduktion
KMP är en mönster-matchande algoritm som söker efter förekomster av ett "ord" W i en huvudsträng "textsträng" S genom att använda observationen att när en missanpassning inträffar har vi tillräcklig information för att avgöra var nästa match kan börja. dra nytta av denna information för att undvika att matcha de tecken som vi vet ändå kommer att matcha. Det värsta fallet för att söka i ett mönster minskar till O (n) .
KMP-Exempel
Algoritm
Denna algoritm är en tvåstegsprocess. Först skapar vi en hjälpgrupp lps [] och använder sedan den här matrisen för att söka i mönstret.
Förbehandling :
- Vi förbehandlar mönstret och skapar en extra matris lps [] som används för att hoppa över tecken medan du matchar.
- Här indikerar lps [] längsta korrekt prefix, som också är suffix. Ett korrekt prefix är prefix där hela strängen inte ingår. Exempelvis är prefix för sträng ABC “” , “A” , “AB” och “ABC” . Korrekt prefix är “” , “A” och “AB” . Suffix av strängen är "" , "C" , "BC" och "ABC" .
Sökande
Vi fortsätter att matcha tecken [i] och pat [j] och fortsätter att öka i och j medan pat [j] och txt [i] fortsätter att matcha.
När vi ser ett missförstånd, vet vi att tecken pat [0..j-1] matchar med txt [i-j + 1 ... i-1]. Vi vet också att lps [j-1] är räknat av tecken på pat [0… j-1] som är både ordentligt prefix och suffix. Av detta kan vi dra slutsatsen att vi inte behöver matcha dessa lps [j-1] -tecken med txt [ij… i-1] eftersom vi vet att dessa tecken matchar ändå.
Implementering i Java
public class KMP {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "abcabdabc";
String pattern = "abc";
KMP obj = new KMP();
System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
}
public int[] computeLPS(char[] str){
int lps[] = new int[str.length];
lps[0] = 0;
int j = 0;
for(int i =1;i<str.length;i++){
if(str[j] == str[i]){
lps[i] = j+1;
j++;
i++;
}else{
if(j!=0){
j = lps[j-1];
}else{
lps[i] = j+1;
i++;
}
}
}
return lps;
}
public boolean patternExistKMP(char[] text,char[] pat){
int[] lps = computeLPS(pat);
int i=0,j=0;
while(i<text.length && j<pat.length){
if(text[i] == pat[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j==pat.length)
return true;
return false;
}
}