Tag Archives: kmp

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)

Replace all occurrences of a pattern in a text by another string

Posted on by

Given a text and a pattern. Replace all the occurrences of the pattern in the text by another given string.

For Example: If text = “aabaabab” and pattern = “ab”. Then after replacing pattern in the text by “abc” the output should be “aabcaabcabc”.

This is a preview of Replace all occurrences of a pattern in a text by another string. Read the full post (463 words, estimated 1:51 mins reading time)