NAME:

LOGIN:

PRECEPTS:

COS 226 Exercises on Substring Search


References: Section 5.3 in Algorithms, 4th edition


1. Give the Knuth-Morris-Pratt DFA for the pattern A A A B A N A A A B A N 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
  |
N |   0    0

2. Give the trace (in the style of the figure on p. 586) of using Boyer-Moore to search for the pattern B L A N C A in the text 

       I  E  A  T  B  A  N  A  N  A  S  W  H  E  N  I  N  C  A  S  A  B  L  A  N  C  A
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 
---------------------------------------------------------------------------------------
       I  E  A  T  B  A  N  A  N  A  S  W  H  E  N  I  N  C  A  S  A  B  L  A  N  C  A

0  5   B  L  A  N  C  A