DFA costruzione nell'algoritmo di Knuth-Morris-Pratt

Question

Mi riferisco al profilo dell'algoritmo Knuth-Morris-Pratt (KMP) per la sottostringa di ricerca nel libro "Algoritmi" di Sedgewick (4 ° ed.).

L'algoritmo KMP utilizza un backup nella ricerca di sottostringa basata su un automa finito deterministico (DFA). Capisco come DFA entra l'algoritmo, ma non capisco come costruire DFA, che è fatto dalla seguente frammento di codice:

dfa[pat.charAt(0)][0] = 1; 
for (int X = 0; j = 1; j< M; j++) { 
    for (int c = 0; c < R; c++) { 
     dfa[c][j] = dfa[c][X]; 
    } 
    dfa[pat.charAt(j)][j] = j+1; 
    X = dfa[pat.charAt(j)][X]; 
} 

dove M è la lunghezza del pattern pat e R la dimensione dell'alfabeto. La funzione charAt() restituisce il valore intero del carattere nella rispettiva posizione.

Qualcuno può spiegare in che modo questa parte di codice costruisce un dfa? Mi sono perso nel significato intuitivo effettivo del ciclo interiore.

Answer 1

Diamo un'occhiata al seguente FA per il modello ACACAGA.

Gli schemi sopra rappresentano rappresentazioni grafiche e tabulari di modello ACACAGA.

Qui, il numero di stati in DFA è M + 1 dove M è la lunghezza del modello. La cosa principale per costruire DFA è ottenere lo stato successivo dallo stato corrente per ogni carattere possibile. Dato un carattere x e uno stato k, possiamo ottenere lo stato successivo considerando la stringa "pat [0..k-1] x" che è fondamentalmente concatenazione di caratteri del modello pat [0], pacca 1 ... pat [k- 1] e il carattere x. L'idea è di ottenere la lunghezza del prefisso più lungo del modello dato in modo tale che il prefisso sia anche suffisso (LPS) di "pat [0..k-1] x". Il valore della lunghezza ci dà lo stato successivo.

Ad esempio, vediamo come ottenere lo stato successivo dallo stato corrente 5 e il carattere 'C' nel diagramma sopra. Dobbiamo considerare la stringa "pat [0..5] C" che è "ACACAC". La lunghezza del prefisso più lungo del modello in modo tale che il prefisso sia il suffisso "ACACAC" è 4 ("ACAC"). Quindi lo stato successivo (dallo stato 5) è 4 per il carattere 'C'.

// dfa[i][j] = k denotes the transition function will go k'th state 
// with character i from state j 

// DFA will go always (i + 1)'th state from i'th state 
//if the character c is equal to current character of pattern 
dfa[pat.charAt(0)][0] = 1; 

// here X is initialized with LPS (longest prefix suffix) 
// of pattern[0....j - 1]. LPS[0] is always 0 
for (int X = 0; j = 1; j< M; j++) { 
    for (int c = 0; c < R; c++) { // for all possible characters 
     // transition function from j'th state taking character c 
     // will go to the same state where it went from X(LPS)'th state 
     // taking character c (justify it with an example) 
     dfa[c][j] = dfa[c][X]; 
    } 
    // DFA will go always (i + 1)th state from i'th state if 
    // the character c is equal to current character of pattern 
    dfa[pat.charAt(j)][j] = j + 1; 
    X = dfa[pat.charAt(j)][X]; // update LPS 
}