algorithm
Knuth Morris Pratt (KMP) Algoritmo
Ricerca…
introduzione
Il KMP è un algoritmo di corrispondenza del modello che cerca le occorrenze di una "parola" W all'interno di una "stringa di testo" S principale impiegando l'osservazione che quando si verifica una mancata corrispondenza, abbiamo le informazioni sufficienti per determinare dove potrebbe iniziare la prossima partita. Approfitta di queste informazioni per evitare di abbinare i personaggi che sappiamo corrisponderanno comunque. La peggiore complessità del caso per la ricerca di un modello si riduce a O (n) .
KMP-Example
Algoritmo
Questo algoritmo è un processo in due fasi. Per prima cosa creiamo un array ausiliario lps [] e quindi usiamo questo array per cercare il modello.
Pre - elaborazione :
- Pre-processiamo il pattern e creiamo un lps array ausiliario [] che viene usato per saltare i caratteri durante l'abbinamento.
- Qui lps [] indica il prefisso corretto più lungo che è anche suffisso.Un prefisso appropriato è prefisso in cui non è inclusa la stringa intera.Ad esempio, i prefissi della stringa ABC sono "" , "A" , "AB" e "ABC" . I prefissi appropriati sono "" , "A" e "AB" . I suffissi della stringa sono "" , "C" , "BC" e "ABC" .
Ricerca
Manteniamo i caratteri corrispondenti txt [i] e pat [j] e continuiamo ad incrementare i e j mentre pat [j] e txt [i] mantengono la corrispondenza.
Quando vediamo una mancata corrispondenza, sappiamo che i caratteri pat [0..j-1] corrispondono a txt [i-j + 1 ... i-1]. Sappiamo anche che lps [j-1] è il conteggio dei caratteri di picchiettio [0 ... j-1] che sono sia il prefisso che il suffisso. Da questo possiamo concludere che non è necessario abbinare questi caratteri di lps [j-1] con txt [ij ... i-1] perché sappiamo che questi caratteri corrisponderà comunque.
Implementazione in 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;
}
}