Figure 3.19 in the exercises of Section 3.4 computes the failure function for the KMP algorithm. Show how, given that failure function, we can construct, from a keyword bib2 • • - bn an. n + 1-state...

Figure 3.19 in the exercises of Section 3.4 computes the failure function for the KMP algorithm. Show how, given that failure function, we can construct, from a keyword bib2 • • - bn an. n + 1-state DFA that recognizes *bib2 • • • bn , where the dot stands for "any character." Moreover, this DFA can be constructed in 0(n) time.

Figure 3.19