DFA-Konstruktion im Knuth-Morris-Pratt-Algorithmus

Question

Ich beziehe mich auf den Entwurf des Knuth-Morris-Pratt (KMP) -Algorithmus für die Substring-Suche in Sedgewicks Buch "Algorithms" (4. Aufl.).

Der KMP-Algorithmus verwendet eine Sicherung in der Substring-Suche basierend auf einem deterministischen endlichen Automaten (DFA). Ich verstehe, wie das EDA den Algorithmus eintritt, aber ich verstehe nicht, wie man konstruieren das EDA, die durch den folgenden Code-Schnipsel getan wird:

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]; 
} 

wo M die die Länge des Musters ist pat und R die Größe des Alphabets. Die Funktion charAt() gibt den ganzzahligen Wert des Zeichens an der entsprechenden Position zurück.

Kann jemand erklären, auf welche Art und Weise dieses Stück Code ein dfa konstruiert? Ich bin in der eigentlichen intuitiven Bedeutung der inneren For-Schleife verloren.

Answer 1

Werfen wir einen Blick auf die folgenden FA für Muster ACACAGA.

Die obigen Diagramme stellen grafische und tabellarische Darstellungen von Muster ACACAGA.

Hier ist die Anzahl der Zustände in DFA M + 1, wobei M die Länge des Musters ist. Die Hauptsache zum Konstruieren von DFA besteht darin, für jedes mögliche Zeichen den nächsten Zustand aus dem aktuellen Zustand zu erhalten. Wenn ein Zeichen x und ein Zustand k gegeben sind, können wir den nächsten Zustand erhalten, indem wir die Zeichenkette "pat [0..k-1] x" betrachten, die im Grunde die Verkettung von Musterzeichen pat [0] ist, pat 1 ... pat [k- 1] und das Zeichen x. Die Idee ist, Länge des längsten Präfix des gegebenen Musters zu erhalten, so dass das Präfix auch Suffix (LPS) von "pat [0..k-1] x" ist. Der Wert der Länge gibt uns den nächsten Zustand.

Betrachten wir zum Beispiel, wie man den nächsten Zustand aus dem aktuellen Zustand 5 und dem Zeichen "C" im obigen Diagramm erhält. Wir müssen die Zeichenfolge "pat [0..5] C" betrachten, die "ACACAC" ist. Die Länge des längsten Präfix des Musters, so dass das Präfix das Suffix von "ACACAC" ist, ist 4 ("ACAC"). Also ist der nächste Zustand (aus Zustand 5) 4 für das Zeichen "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 
}