Algorithm for finding and replacing a pattern in a given string or paragraph

0 / 1418
find and replace

Continuation of my previous blog 


#define SIZE 2

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

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", replaceStr[] = "News find";
	int *retVal;
	retVal = findAndReplaceSubString(str, substr, replaceStr);
	puts("*************The original string string is: ************");
	printf("\nAbove string after replacing all occurances of '%s' with '%s' in it:\n\n", substr, replaceStr);
	return 0;

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

int* findAndReplaceSubString(char str[], char substr[], char replaceStr[]) {
	int i = 0, j = 0,
	strLength = strlen(str), 
	substrLength = strlen(substr),
	replacestrLength = strlen(replaceStr),
	modified_substring_length_diff = strlen(replaceStr) - substrLength,
	modified_string_length = strLength;

	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));
					modified_string = (char*)realloc(modified_string, (strLength+(length+1)*(replacestrLength - substrLength))*sizeof(char));
					if (more_indices != NULL) {
					    memcpy(more_indices, indices, length);
					    indices = more_indices;
					    indices[length++] = j;
					    modified_string_length = strlen(modified_string);
					    if ( modified_string_length == 0) {
					        strncpy(modified_string, str, j-1);
					        strcat(modified_string, replaceStr);
					        strcat(modified_string, str+j+substrLength);
					    else {
					        modified_string[j-1+(length-1)*(replacestrLength - substrLength)] = 0;
					        strcat(modified_string, replaceStr);
					        strcat(modified_string, str+j+substrLength);
	if (length == 0) {
	    return NULL;
	return indices;

Demo for the above code is here


Please comment if you have any doubts in the above algorithm. Subscribe to our blog for more interesting stuff.



An avid reader, responsible for generating creative content ideas for His interests include algorithms and programming languages. Blogging is a hobby and passion.