//UPDATED VERSION..Minor changes in delete and insert functions..


// Input three strings s, t and w from the user. Assume that the strings do not
// contain blank or any whitespace character.Write a function that finds all occurrences 
// of substring t in s, and replaces them by w. The function returns the number 
// of such occurences or replacements.Note that t and w can be of different sizes.
//Author:rahule@cse.iitk.ac.in

#include<stdio.h>
int replace_substring(char *, char *, char *);
void delete(char *,int ,int);
void insert(char *,char * ,int);
int string_length(char *);
main()
{
  char t[50],s[50],w[50];
  int cnt;
  //entering the strings
  printf("\nEnter the string S :");
  scanf("%s",s);
  printf("\nEnter the string t :");
  scanf("%s",t);
  printf("\nEnter the string w :");
  scanf("%s",w);
  //calling the function
  cnt= replace_substring(s,t, w);
  printf("\n%d number of instances were found and replaced..\nThe new string is :'%s\n'",cnt,s);
}

int replace_substring(char *s, char *t, char *w)
/*function accepts three strings s t w and replaces all the instances of t in s with w */
{
  int k,j,cnt=0,flag;
  for(j=0;j< (string_length(s) - string_length(t)) ;j++)	
    {
      flag=0;		
      for(k=0;k<string_length(t);k++)		//checks whether the string starting from s[j] is t or not
      {
	if(s[j+k]!=t[k])	//if not,set flag as 1 and break..ie string starting from s[j] is not equel to t
	{
	  flag=1;
	  
	  break;
	}
      }
      if(flag==0)	//ie, a match is found.there is a 't' at the index j of string 's'
      {
	delete(s,string_length(t),j);	//deletes the substring 't',which is at index j
	insert(s,w,j);			//inserts new string 'w' at j
	cnt++;				//increases the count by one
      }
    }
    return(cnt);
}

void delete(char *s,int length,int index)
/*function to delete a substring of length "length" from the index 'index' of the given array 's'   */
{
  int j;
  for(j=index;s[j]!='\0';j++)		//shifts all the elments after the substring 't' to left,by an offset 'length(t)',thus removing t from s
  {
    s[j]=s[length+j];
  }
  s[j]='\0';
}

void insert(char *s,char *w,int index)
//function to insert a new string 'w' to string 's' at the index 'index'    */
{
  int j,l=string_length(w);
  
  for(j=string_length(s);j>=index;j--)	//makes room for w by shifting all the lements starting from 'index' by an offset "length(w)" to right
    s[j+l]=s[j];
  
  for(j=0;j<l;j++)		//insets the string "w" to newly created space
    s[index+j]=w[j];
}

int string_length(char *s)
//funtion to find the string length
{
  int i;
  for(i=0;s[i]!='\0';i++);	//loop till the end of string
  return(i);
}