I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say:
The key observation is that the characters in the text that would need to be rescanned are precisely
pat.charAt(1)
throughpat.charAt(j-1)
: we drop the first character to shift right one position and the last character because of the mismatch.
I can't understand the above, for example. If the pattern is ABABAC, and the text string is ABACABABACA. and there are two pointers i and j for text string and pattern respectively.
If $i=3$, the character $c$ in the text string is mismatch, where the pattern is $b$. then we need to rescan from the beginning of the pattern. not the second character : pat.charAt(1)
.
I think I am misunderstanding what the author intended to express. What does the author mean?