• Write the pseudo-code for a string-matching algorithm of your choice. Note that it is perfectly fine if you choose either the Bruteforce or Rabin-Karp algorithm which were discussed in class. If you use one of these algorithms, your pseudo code could look very similar to the one shown in the slides. You are encouraged to modify the pseudo-code to make it more detailed and closer to your real implementation, but having the pseudo-code similar to what is in the slides is Okay and points won't be deducted for that.
• Follow the steps in your pseudocode, and implement the string-matching algorithm using Python.  Implementations in other programming languages are also acceptable such as R, Java, or C/C++.
• Analyze the worst-case time complexity for the string-matching algorithm that you have implemented.

What to submit:

• pseudo-code that you wrote
• worst-case time complexity analysis using the pseudocode, including the exact number of steps (or basic operations), and/or the big-O and big-Theta estimates.
• source code for your implementation of the algorithm
• screenshots of your program running and its outputs for at least three different test inputs. If you are using Jupyter Notebook for your implementation of the algorithm, you could submit the .ipynb and .html versions of the notebook instead of screenshots. Make sure that you show outputs for at least three different inputs.
•   

 

Rabin-Karp Pseudo-Code FINDMATCH_RABIN-KARP(text, pattern) // Input: text: a string that is a large body of text; pattern: a string that is a specific text pattern // Output: location of the pattern in text; return NULL if pattern is not found in text M length of pattern hash_phash value of pattern hash_t hash value of first M letters in text do if (hash_p: hash_t) brute force comparison of pattern and selected section of text else == hash_t hash value of next section of text, one character over while (brute force comparison== true or end of text)