Write a program (matching.cpp) which finds all occurrences of a given pattern within a text file using the Morris-Pratt algorithm. Instrument your algorithm to count the number of character comparisons performed. Extend your program to run two searches, the first using the original Morris-Pratt algorithm, and the second with extensions based on the character in the text that failed to match (the Knuth Morris-Pratt algorithm). Output the total number of comparisons performed in each case.

Input

The name of the file and the pattern itself should be read directly from standard input, in that order. Example: Filename a one line ASCII pattern potentially involving spaces

Output

For each algorithm, you should output The number of occurrences of the pattern in the text The position in the text where the first 10 occurrences of the pattern were found. Don't worry about trying to work out line and column numbers, the position should be the index in the file, so for example a position of 0 indicates that the pattern appears at the very beginning of the file. The number of character comparisons performed.

Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.