Horspool's Algorithm

[Audio] Hello everyone, my name is Anthony Roman and my presentation will be about Horspool's Algorithm. I hope you enjoy it!.

[Audio] Nigel Horspool it's originally from Great Britain, he moved to Canada where he lived the majority of his life. He has a PhD in computer science and it's a retired professor from University of Victoria in British Columbia. He created the Horspool's algorithm in 1980, it's a simpler version of the Boyer-Moore algorithm created in 1977..

[Audio] The Horspool's algorithm helps the user to find a specific word in a sentence, it takes a substring and will compare it to a whole string until the substring matches the specific word in the string..

[Audio] Using the image as an example, you start by creating a match table with the substring you want to search in the whole string. In this case the substring it's a,b, c,d and the whole string it's e,o, v,a,d,a, b,c, d, f, t, o,y. This particular algorithm will start comparing both the subtring and string at the beginning starting with the last character of the substring. As seen in the image a and d don't match so the substring will move the position stated in the match table in this case 3 positions. This will continue until all characters in the substring match the string..

[Audio] Here is a sample code that uses Horspool's algorithm to search for a substring A,B, C in a string of A, B,A,A,A,B,C, D. At the end the pattern matched when the substring shifted 4 places in total. The first time that shifted it moved 2 places and then when it compared again and did not matched then it moved 2 places again and then it matched. That is why it took 4 places in total. The time complexity is big O of n times m, where the n is the whole string and m it's the substring..

[Audio] Well that it's all from my part, hope everyone liked it. Horspool's algorithm it's a great tool to use and we see it every day in things like autocorrect and word searches etcetera. Good luck to all and have a great day..