NAME:

LOGIN:

PRECEPTS:

COS 226 Exercises on Substring Search


1. Give the Knuth-Morris-Pratt DFA for the pattern A A A B C A A A A B C B over the three-letter alphabet by filling in the table below. 


  |   0    1    2    3    4    5    6    7    8    9   10   11
--------------------------------------------------------------
A |   1    2
  |
B |   0    0
  |
C |   0    0

2. Give the trace (in the style of the figure on p. 692) of using Boyer-Moore to search for the pattern W O R S T in the text 

       I  T  W  A  S  T  H  E  B  E  S  T  O  F  T  I  M  E  S  I  T  W  A  S  T  H  E  W  O  R  S  T  O  F  T  I  M  E  S
by completing the trace below. 


i  j   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
--------------------------------------------------------------------------------------------------------------------------
       I  T  W  A  S  T  H  E  B  E  S  T  O  F  T  I  M  E  S  I  T  W  A  S  T  H  E  W  O  R  S  T  O  F  T  I  M  E  S

0  4   W  O  R  S  T