4
$\begingroup$

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) through pat.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?

$\endgroup$
4
$\begingroup$

Sedgewick continues: "These are pattern characters that we know, so we can figure out ahead of time, for each possible mismatch position, the state where we need to restart the DFA."

What I understand is that this quote tries to explain that if you encounter a mismatch at letter at position $j$ of the pattern you have to shift the patterns by one position against the text and see where that leads us. The point there is that we do not need to know the actual text at that moment, because we know that so far the patterns has matched the text and we can match the pattern to itself (shifted).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.