Checkpoint L$2\mathrm{.}1-$ Brute Force

The task for Checkpoint $7$ is to implement your own version of

the brute force algorithm and compare it to the built$-$in

indexOf of the Java String class. Create a new class that

extends the StringMatcher and overrides the required methods

to implement the brute force algorithm.

You should instantiate your new class for the $$bruteforce$$

case of the algorithm switch statement, for example, you should

change

case "bruteforce":

matcher $=$ null; $//$ TODO: Checkpoint $7$

break;

to

case "bruteforce":

matcher $=$ StringMatcherBruteForce$()$; $//$ Checkpoint $7$

break;

For reference, the brute force text search algorithm:

T $=$ target search string

P $=$ pattern to search for

n $=$ length of T

m $=$ length of P

for $($ int i $=0$; i $<=$ n $$ m ; i$++)\{$

int j $=0$ ;

while $(($ j $<$ m $)$ && $($ T$[$ i $+$ j $]==$ P$[$ j $]))\{$

j$++$;

$\}$

if $($ j $==$ m $)\{$

return i;

$\}$

$\}$

return $-1$;

Test your program on several known input files $($including the

ones already in $/$data$).$ It may be easier to debug your program

if you use a smaller target text where you can calculate the

correct position of the pattern and the number of steps you$$re

your algorithm should be performing. Remember to test with

both short and long patterns and also patterns that do not exist.

You can always make use of the built$-$in implementation to find

out the correct position of the pattern $($but not the number of

steps$).$

The automated test will test your implementation of the brute

force algorithm on various target and pattern texts, running in

$$non$-$verbose$$ mode.

Can you beat the Java builtin string comparison!!!??

Checkpoint L$2\mathrm{.}2$ Better String Matching with Boyer$-$Moore

Implement the Boyer$-$Moore algorithm as discussed in

lectures. You should attempt to implement the algorithm

yourself, but you are allowed use the wonders of the Internet as

a resource $($and the lecture slides, there is pseudo code

there$).$ However, please do include the reference to the source

of your implementation and it must conform to the

implementation above and include the number of character

comparisons.

Checkpoint L$2\mathrm{.}3$ Better String Matching with KMP

Implement the Knuth$-$Morris$-$Pratt algorithm as discussed in

lectures. You should attempt to implement the algorithm

yourself, but you are allowed use the wonders of the Internet as

a resource $($and the lecture slides$).$ However, please do include

the reference to the source of your implementation and it must

conform to the implementation above and include the number

of comparisons.

There are variants of the KMP algorithm so be sure to

implement the lookup table as described in the lectures to

get the correct number of comparisons