The repository contains code to load a file with the target

string, ExactStringMatchingDriver, and an intended class

structure for the online algorithms via an abstract

class StringMatcher, which has the abstract methods

$$ void setTarget$($String target$)$ sets the target to

search within

$$ void setPattern$($String pattern$)$ sets the pattern to

search for

$$ int match$()$ searches for the pattern in target, returns

the index of the first match or $-1$ if there is no match

$$ int getNumberOfSteps$()$ returns the number of steps

performed during a match

Your task is to extend the abstract StringMatcher class and

override these methods to implement the online string matching

algorithms. StringMatcher contains other methods that times

the execution of the setTarget, setPattern and match

methods $(*$timed$()).$ These timing methods are called from

ExactStringMatchingDriver class to perform the searching.

You are also provided with a sample implementation

of StringMatcher called StringMatcherBuiltin that uses

the String class method indexOf. Examine its contents to see

how the above methods should be implemented.

The first line of standard input specifies a command. The first

command argument specifies the name of the file that contains

the text to search, the target string. The repaper.txt file

contains the target from the tutorials and you can attempt to

search for REPAPER.

The second command argument specifies the algorithm to

use, by default this is "builtin" and uses the

StringMatcherBuiltin class. The switch statement takes this

parameter and instantiates the corresponding class that

represents an implementation of an algorithm: builtin,

bruteforce, bm$,$ or kmp$.$ It is your job to implement

bruteforce $($ch$7),$ bm $($ch$8),$ and kmp $($ch$9).$

For example, run the ExactStringMatchingDriver class to

use the builtin string matching and enter REPAPER as the

pattern $($user input indicated with $<--$ user input$)$:

java $$jar ExactStringMatchingDriver

Enter command: repaper.txt$,$ builtin, verbose $<--$ user input

Enter search term: REPAPER $<--$ user input

index: $34,$ comp: $-1,$ Target: $0\mathrm{.}004346$ms$,$ Pattern:

$0\mathrm{.}004345$ms$,$ Match: $0\mathrm{.}010271$ms$,$

Total: $0\mathrm{.}018962$ms

Enter search term: REPAPER

index: $34,$ comp: $-1,$ Target: $0\mathrm{.}004346$ms$,$ Pattern: $3\mathrm{.}95$E$-4$ms$,$

Match: $0\mathrm{.}002766$ms$,$

Total: $0\mathrm{.}007507$ms

Enter search term: $<--$ user input

The program terminates when an empty line is entered.

Note that the runtime will be different on your own machine and

that the first search time maybe inaccurate $($or at least longer$).$

Note that the number of comparisons is $-1$ as the builtin

implementation is a blackbox. For your implementation you

should provide the number of character comparisons

made by the algorithm.

There are a number of other target text files in the data

directory that should be familiar from the lectures and you can

evaluate the runtime and number of comparisons on those files

as well.

Checkpoints

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.