Description
We want to use KMP Algorithm to perform string matching.
Please refer to Section 2.6.2 of "Fundamentals of Data Structures in C++, 2nd Edition" by Horowitz et al. for the details about the algorithm.
Please note that some modifications to algorithm provided by the textbook are required:
- We need our program to report all matched patterns, instead of only the first one. This requirement means that our program should appropriately leverage the failure function knowledge to resume the search routine not only after a mismatch but also after each succesful pattern match.
- We need our program to show the procedure of the searching algorithm.
Input
The first input integer is the number of string pairs.
String pairs follow the integer.
Each string pair comprises 1) a pattern string and 2) a content string. We want to search the content string for the existence of the pattern string.
Output
Our program needs to print 1) the pattern string, 2) the failure function of the pattern string, 3) the content string, 4) the procedure of the searching algorithm, and 5) the number of patterns found in the content string.
The 4) procedure part uses four types of symbos, '~', '=', 'o', and 'x', to denote four possible situations confronted by the searching algorithm.
KMP Algorithm uses two pointers to iteratively compare the the pattern string and the content string.
'=' denotes that the two charcters pointed by the two pointers are matched.
'o' denotes that the two charcters pointed by the two pointers not only are matched but also result in a matched pattern.
'x' denotes a mismatch between the two pointers.
'~' denotes a partial-matched character that the failure function table informs the algorithm.
The following figure shows the screenshot of sample output. In the "Sample Output" section, all the ' ' (space) characters in the sample output are replaced with '.' (period) for the sake of clarity. Our program should use spaces as delimiters instead of periods. Usually there are multiple pairs of strings in an input stream. Our program should use two newline characters to seperate the outputs corresponding to different string pairs.
