The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size.But, All the textbooks directly give the final Pratt Algorithm.  Below is the code ( the code is not really needed to answer the question) which is more or less similar to original Knuth's Algorithm ( full code) , And it builds the DFA.My Question is, How can we (idea behind) arrive at the final current version ( Pratt optimization) from below DFA version ? Also, Is it called minimization of DFA, But DFA minimization can be applied to a specific alphabet(regular language), Here it applies to all alphabets ?public KMP(char[] pattern, int R) {     // build DFA from pattern, R is the language length    int M = pattern.length;    dfa = new int[R][M];     dfa[pattern[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];     // Copy mismatch cases.         dfa[pattern[j]][j] = j+1;      // Set match case.         X = dfa[pattern[j]][X];        // Update restart state.     } }
KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm
algorithms;automata;search algorithms;strings