Implement the Horspool pattern-matching algorithm found in your textbook (section 7.2) in either Java or C++.

When you studied Brute force algorithms, you saw an example of pattern matching which examining a text for a pattern character by character. Once a mismatched character wasfound, the pattern shifted down only by a single character. With this algorithm, the input data is pre-processed to speed up the pattern matching. When there is a mismatched character between the text and the pattern, a shift is made based on the mismatched characters and the position of that character in the pattern that is being sought.

First, write the code to create the shift table. Second, write the code to do the searching using the shift table. Third write a driver that allows the user to enter text (could be nonsense or a real sentence. Then allow the user to enter the pattern to find in the text. The result of whether the pattern was found or not and if found, at what starting position of the text.

Loop to allow the user to enter another text and pattern pair.

The user will enter the search pattern from the keyboard. Report to the user how many times the pattern was located and which line numbers and positions within those line numbers the pattern was found.

Ie: the pattern eat was found: on line 1 starting at positon 4 on line 5 starting at position 5