Knuth-Morris Pratt Algorithm

This week has been mostly reading and researching. I am trying to learn how to use the command prompt for the SQL server I made last week. Command line programming is a fast and easy way for the user to perform specific tasks. This scripting language is easy to automate because it requires very few resources. For example, simply write mysql> show databases\g to view the data.

As I continue to work on the rows and columns for my database, I have started thinking about the actual algorithm itself. The Knuth-Morris Pratt algorithm is a searching algorithm that looks for occurrences of a pattern in a text string.

Let’s say the text string is abcdefgbobbyasdfjkl and the pattern is bobby. The program will look at the first element of the pattern and will compare it to the first element of the text string. It is not a match (a, b) so it will move to the next element in the text string and compare it to the first element of the pattern. It is a match (b, b), so the program will advance to the next element in both the text string and the pattern. It is not a match (c, o) so the program will restart the search from the next element in the text string, but will still be looking at the first element from the pattern (d, b). Once a match is found, it moves to the next element in both the text string and the pattern to continue comparing. It stores the indexes of the elements in an array, which can be called or modified later in the program.

I will use this searching algorithm to read through lines of text and will set the pattern to be the days of the weeks. This will return important days for the tasks and upcoming assignments that I want to find. I think this is a good starting point for picking up the day of a task through emails. Hopefully I can get the date soon!

Thank you for reading!