Algorithm to find substring within a string or a paragraph
Often we come across interview questions like , find all occurances of a given substring within a string.
What are the best possible strategies to solve this problem ? Well, there could be many but today in this blog
I will consider explaining the simplest and most straightforawrd way of looking for a substring within a given
string and it’s linear search (costly though, but this algorithm can be optimized).
Below is a small C program that explains the solution to the above problem:
Below is the link to compile and execute the above code:
Substring pattern match
Let’s try to understand what the above program does:
It has a nested loop. The outer loop loops through the given string parsing the string character by character.
The inner loop parses the substring character by character and looking for a possible match of it’s first character
to that of the current character of the main string. If the characters match, it does a stnrcmp() wherein it will
compare N characters (N = length of substring) starting from current index and if a match is encountered, the index is
pushed into the array. This iteration goes till the length of the main string.
This algorithm can be further extended to create a find and replace functionality which will be the topic of my next
blog. Stay tuned for more interesting stuff and please comment if there are any doubts in this one.