- Teacher: Admin Utilisateur
String Matching Algorithms (Free)
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.