This is the first in a series of computer science lessons about string matching algorithms and how to implement them. String matching is not just about text processing, it has applications in the fields of artificial intelligence, cybersecurity and bioinformatics, to name but a few. String matching algorithms include the naive algorithm, KMP, Boyer Moore and Rabin Karp. Some of these are particularly suited to specialist applications like DNA sequencing, data mining and network intrusion detection systems.

In this lesson, you will learn about a simplistic approach, to the problem of searching for one string of characters within another. This is often referred to as the naive algorithm. You will learn that the naive approach has its uses, but it also has several limitations; Depending on the nature of the data being processed, it may waste time performing unnecessary checks; the input string is scanned forwards and backwards which requires extra code to buffer it if it is being streamed from an external file; and the implementation code has quadratic time complexity which is problematic for large data sets.

It is important to familiarise yourself with the naive approach because it will help you to understand, implement and adapt the more sophisticated algorithms such as KMP and Boyer Moore. These are covered in detail in later lessons.

Chapters:
00:00 String matching applications
00:42 String matching terminology
01:35 The naive algorithm
05:14 Limitations of the naive algorithm

Acknowledgments
Humanoid Robot video clip by afnan king from Pixabay.com
Robot vacuum cleaner video clip by cottonbro studio from pexels.com
Network switch video clip by Ciprian Cucuruz from Pixabay.com
Test tubes video clip by Lumos Ajans from Pixabay.com
Woman in a laboratory video clip by Pavel Danilyuk from pexels.com
DNA animation video clip by Manil Doomra from Pixabay.com
Typing into a computer video clip by Mikhail Nilov from pexels.com