Tag Archives: string matching

linear time string matching using KMP matching algorithm

Posted on by

Given an input string S and a word w. Find the occurrences of the word w in the given string S in linear time. In other words, explain the linear time string matching using KMP matching algorithm.

For example, if S = “ABABAABA” and w = “ABA” then there are 3 occurrences of w in S at {0, 2, 5}.

This is a preview of linear time string matching using KMP matching algorithm. Read the full post (1652 words, 1 image, estimated 6:36 mins reading time)