The native string-matching algorithm

1. Be sure to produce a test driver program in a separate file/class from your algorithm program a. (as demonstrated by examples posted for TestInsertionSort.java and InsertionSort.java)

2. You should be able to read test data from a file a. (as demonstrated by example data input for TestInsertionSort)

3. Be sure to follow the delivery instructions

a. try to limit wrapped lines and prevent truncated lines in your printed output;

b. test case statements and test case results (NOTE: test your program with at least the data in the following figures

The naive algorithm finds all valid shifts using a loop that checks the condition PIl m] Tls l s ml for each of the n m 1 possible values of s ATCHER (T, P) NAIVE-STRING-M 1 n T. length 2 m P. length 3 for 0 to n m if P[1.. m s m] 5 lab2576298 d55coa 10e065 dcee06 print "Pattern occurs with shift" s Figure 32.4 portrays the naive string-matching procedure as sliding a template" containing the pattern over the text, noting for which shifts all of the characters on the template equal the corresponding characters in the text. The for loop of lines 3-5 considers each possible shift explicitly. The test in line 4 determines whether the current shift is valid; this test implicitly loops to check corresponding character positions until all positions match successfully or a mismatch is found. Line 5 prints out each valid shift s Procedure NAIVE-STRING-MATCHER takes time O(n m 1)m), and this bound is tight in the worst case. For example, consider the text string a" (a string of n a's and the pattern am. For each of the n m 1 possible values of the shift s the implicit loop on line 4 to compare corresponding characters must execute m times to validate the shift. The worst-case running time is thus O((n m 1)m), which is o(n?) if m Ln/2 Because it requires no preprocessing NAIVE STRING-MAT CHER's running time equals its matching time