String Matching 1. The Naive Algorithm

[@kerowagdy9417]

I love the way you simplify and explain algorithms.. it seems to be a great series that I was searching for ❤
Keep up the awesome work 👏

[@ComputerScienceLessons]

Thank you. Your comment is much appreciated :)KD

[@RobertFletcherOBE]

really interesting start, I'm looking forward to the more optimal methods. would you consider explaining string similarity?

[@ComputerScienceLessons]

KMP next. Then Boyer Moore. I'm digging at the moment to find out more about Gilbert and Riordan; I think their influence was profound but, as Knuth once said, "An algorithm must be seen to be believed" :)KD

[@naamnhibataunga5897]

will you not discuss z algorithm?

[@ComputerScienceLessons]

I will, now that you have mentioned it. While developing their algorithm, Knuth, Morris and Pratt were aware of the Z-algorithm, which was invented by Edgar Gilbert and John Riordan in 1958. Insights and ideas from the Z-algorithm (pre-processing the string you want to find) no doubt contributed to the thinking that led to the KMP algorithm. Interestingly, I teach a very talented 15 year old student who loves coding. She asked me for a challenge so I suggested she write a string matching program. She independently came up with the idea of preprocessing the string being search for :)KD

[@stephenhemingway9435]

Why does the input string pointer move back to A and not C, when the pattern pointer moves back to C?

[@AndrewMellor-darkphoton]

hi

[@ComputerScienceLessons]

Hi