KMP Algorithm

Estimated Time

2.5 hour

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:

  • Search for a pattern in the string using naive string search method.
  • Find the Lowest-Prefix-Suffix array for a search pattern by preprocessing
  • Given a search string and a pattern to search in that string, you will be able to search for that pattern in the search string using KMP algorithm
  • Understand the intricacies of KMP algorithm and Naive string searching algorithm.