This is the second 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 the previous lesson, you met a naive approach to the problem of searching for one string of characters within another. In this lesson, you’ll learn how to write a program to implement the naive algorithm. The program is described with pseudocode first, then written in VB.NET. The lesson also includes equivalent code in C# and Python.

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 Introduction
01:04 Pseudocode
03:02 Implementation 1 with VB.NET
06:10 Limitations
06:52 Quadratic time complexity
07:27 Implementation 1 with C#
07:44 Implementation 1 with Python
08:01 Implementation 2 with VB.NET
09:16 Implementation 2 with C#
09:25 Implementation 2 with Python
09:31 Built in methods