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 :

  1. Pre-processiamo il pattern e creiamo un lps array ausiliario [] che viene usato per saltare i caratteri durante l'abbinamento.
  2. 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

  1. 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.

  2. 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;
    }

}


Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow