There is one point I don't understand in the DFA construction for mismatch cases.

Here is the lecture note I watched, which describes how to handle mismatched characters during the DFA construction process.

enter image description here

Some information about the presentation screen shot:

pat is the pattern, string index starts at 0, dfa is the state transition table, in which the row is indexed by the character(eg, "A","B" or "C"), column by state(1,2,3,...).

My question starts:

In the place in the presentation, where starts with "To compute dfa[c][j]", it says run the simulation using the last j-1 chars.

I am confused:

Why run the simulation using the last j-1 chars, rather the last j chars.

What's the intuition of this design?


2 Answers 2


Say we are at state j (in the question's example, j is 5). This means that so far we have successfully matched j characters (characters 0 to j-1 of the pattern). Now, we receive a new character - call it newChar.

Case 1: newChar is the character we wanted ('C' in the example). All is good and we have now a match of j+1 characters (characters 0 to j of the pattern).

Case 2: newChar is not the character we wanted. Let's assume the most optimistic situation: that we've now matched j characters of our pattern. (We couldn't have a match of j+1 characters in this case, because otherwise we would be in Case 1.) The last of these j characters that we matched is newChar. To have a total of j characters matched, then, we must have matched characters 1 to j-1 of the pattern plus newChar.

Because a mismatch puts us in Case 2, and Case 2 only uses characters 1 to j-1, we need only run the simulation using the last j-1 characters.


by "simulate" it mean just run the partially built DFA (in your mind) on the last $j-1$ characters of the pattern. When we are in state $j$ the first $j-1$ characters of the pattern have been matched but the current DFA does not know a transition for state $j$ and the character under consideration, so we decide what would be the next state. If it is B we don't want DFA to restart, but instead start from state 4. This avoids going back in the input.

The intuition is exploiting the matchings between some prefix of the pattern and the suffix of an extension of that prefix. Whenever a mismatch occurs the algorithm does not need to go back in the input since the DFA remembers all partial matchings so far.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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