Pattern Search Algorithm- KMP

A Quick Overview

Pattern Searching algorithms, also known as String Matching algorithms, are very useful when searching for a string within another string.

Introduction to Pattern Search Algorithm

Given a text str[0..n-1] and a pattern pat[0..m-1], write a program with a function PatternSearch(char pat[], char str[]) that prints all occurrences of pat[] in str[]. Given that n > m.

Problem Statement

1. Iterate over string for i from 0 to n – 1 (n = string size).  2. For every value of i, slide pattern over text one by one & check for match.   3. If there’s match, slide by 1 to check for subsequent matches.

Native Approach

Time Complexity (Best Case): O(n)   Time Complexity (Worst Case): O(m*(n-m+1))   Space Complexity: O(1)

KMP utilizes the deteriorating property and further reduces the running time complexity of the most pessimistic scenario to O(n).

KMP Pattern Searching

Time Complexity (Worst case): O(n) where n is length of text.  Space Complexity: O(m) where m is the size of pattern.

How to implement this approach in different programming languages?