Description
Part A:
1. Implement Horspool’s String Matching Algorithm using C or C++ or Java. (100 pts)
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, where the first line
contains the string of pattern, and the second line contains the string of text
(b) You can assume that all characters in both the pattern and text belong to 26 letters of English
alphabet plus the space
(c) Your code will produce an output ASCII file named ‘output.txt’, which contains the index of the
left end of the first matching substring or -1 if no match
(d) Your code should output the execution time for running the algorithm excluding time of input/output.
(e) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
Bonus question: Implement Boyer-Moore’s String Matching Algorithm using C or C++ or Java (40
pts) Requirements:
1. Your code should be able to read an input ASCII file named ‘input.txt’, where the first line contains
the string of pattern, and the second line contains the string of text
2. You can assume that all characters in both the pattern and text belong to 26 letters of English alphabet
plus the space
3. Your code will produce an output ASCII file named ‘output.txt’, which contains the index of the left
end of the first matching substring or -1 if no match
4. Your code should output the execution time for running the algorithm excluding time of input/output.
5. A script file or readme file including the instructions to compile and run the code should be submitted
together with the codes
2
