(1) Draw the Matching-Automaton for the string ano".

(2) Run this automaton over the string \banananona" by giving the sequence of states that the automaton reaches at each position of the string.

(3) Draw an automaton for an*o", where \*" denotes a wildcard, i.e., it matches any character. Use a transition labeled x for the wildcard character, denoting that variable x equals the read letter. In other transitions you may test x, e.g., the transition \a; x = b", denotes that the current letter is a and the wildcard character was b. | In the worstcase, what is the size of an automaton for a pattern of length m containing w-many wildcards, using an alphabet of size k?

(4) Run the Boyer-Moore and the Horspool algorithms for pattern ano" over string \banananona". How many comparisons of characters are applied in total for each algorithm?

(5) Adapt the KMP algorithm so that it can deal with patterns that contain wildcards. Calculate the worst-case running time of your new algorithm.