KMP算法中DFA的构造
以下内容转载自https://stackoverflow.com/questions/30548170/dfa-construction-in-knuth-morris-pratt-algorithm，帮助理解KMP算法中根据模式串构造DFA，以及与LPS的关系 Question I am referring to the outline of the Knuth-Morris-Pratt (KMP) algorithm for substring search in Sedgewick’s book “Algorithms” (4th ed.). The KMP algorithm uses a backup in substring search based on a deterministic finite automaton (DFA). I understand how the DFA enters the algorithm, however I don’t understand how to construct the DFA, which is done by the following code snippet: 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]; } where M is the the length of the pattern pat and R the size of the alphabet. The charAt() function returns the integer value of the character at the respective position. ...