Algorithm to find substring within a string or a paragraph

0 / 1541

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:

``````#include
#include
#include
#define SIZE 2

int* findSubString(char[], char[]);
void print (int*);
int *indices = NULL, *more_indices = NULL, length = 0;

int main(void) {
char str[] = "Contrary to popular belief, Lorem Ipsum is not simply random text. It has roots in a piece of classical\
Latin literature from 45 BC, making it over 2000 years old. Richard McClintock, a Latin professor at\
Hampden-Sydney College in Virginia, looked up one of the more obscure Latin words, consectetur, from a\
Lorem Ipsum passage, and going through the cites of the word in classical literature, discovered the undoubtable\
source. Lorem Ipsum comes from sections 1.10.32 and 1.10.33 of 'de Finibus Bonorum et Malorum' (The Extremes of Good and Evil)\
by Cicero, written in 45 BC. This book is a treatise on the theory of ethics, very popular during the Renaissance.\
The first line of Lorem Ipsum 'Lorem ipsum dolor sit amet, comes from a line' in section 1";

char substr[] = "Lorem";
int *retVal;

retVal = findSubString(str, substr);
if (retVal != NULL) {
printf("Substring \'%s\' is found in string \'%s\' at index/indices: ",substr, str);
print(retVal);
}
else {
}
return 0;
}

void print(int *arr) {
int index = 0;
for (index = 0; index < length; index++) {
printf("%d ", indices[index]);
}
}

int* findSubString(char str[], char substr[]) {
int i = 0, j = 0,
strLength = strlen(str),
substrLength = strlen(substr);

for (i = 0; i < substrLength; i++) {
for (j = 0; j < strLength; j++) {
if (substr[i] == str[j]) {
if (strncmp(str+j, substr, substrLength) == 0) {
more_indices = (int*)realloc(indices, SIZE*sizeof(int));
if (more_indices != NULL) {
memcpy(more_indices, indices, length);
indices = more_indices;
indices[length++] = j;
}
}
}
}
}

if (length == 0) {
return NULL;
}

return indices;
}``````

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.