CareerCup

#include <iostream>
#include <cstring>
using namespace std;
char* findReplace(char* str,char* find,char* replace)
{
    char *ind,*next,*str_p;
    char temp[30];
    int f=strlen(find),r=strlen(replace);
    str_p=str;
    while((ind=strstr(str_p,find))!=NULL)
    {
        next=&ind[f];
        strcpy(temp,next);
        ind[0]='\0';
        strcat(str,replace);
        strcat(str,temp);
        str_p=ind+r;
    }
    return str;
}
main()
{
    int k;
    char str[30],str1[10],str2[10];
    do {
    cout<<"Enter original String:";
    cin>>str;
    cout<<"Enter String to be replaced:";
    cin>>str1;
    cout<<"Enter String to be replaced with:";
    cin>>str2;
    cout<<"String after modification is:";
    cout<<findReplace(str,str1,str2);
    cout<<"\nDo you want to stop,1 for yes and else for no:";
    cin>>k;
    } while(k==1);
}

What about complexity?
It` not quite simple to use KMP algo at interveiw

For finding KMP would be the one to use. However for replacing what are the constraints? The replacement string can be longer or shorter or same size? If it can be longer we will have to count the number of occurrences (you will use this info to decide the length of the new string) and make note of the places that it was found and then start the copying from the old string to the new string.

And if they are making people implement KMP during interview that's would be hard on the interviewee.

sounds like a trick question - ambiguous
how will you find "aa" and replace with "aaaa" in string "aaaa"?
what is the expected out?

As I mentioned, it was asked in a written test not in an interview. Nothing was mentioned about complexity, but two examples of I/O were given :

with equal length:
I:"abcdefgcdhijkl"
F:"cd"
R:"pq"
O:"abpqefgpqhijkl"

and with unequal length

I:"abcdefgcdhij"
F:"cd"
R:"pqrs"
O:"abpqrsefgpqrshij"

Why not use hash function.
Search for the first matching character in the string and then find the hash of the substring and the string. If found replace it.
Time complexity = O(n)

#include<iostream.h>
#include<string.h>

char* findReplace(char* src, char* find, char* replace)
{
int s,f,r,len,i,j,k,x,y;
char z[20];

s=strlen(src);
f=strlen(find);
r=strlen(replace);

i=0;

while(i<s)
{
for(j=i,k=0;k<f;k++,j++)
{
if(src[j]!=find[k])// comparing substring in src and 'find', character by character
break;
}

if(k!=f)//If substring doesn't match with 'find', increment i to start comparing from the next character.
{
i++;
}

else// substring and find matched
{
if(r==f)// case 1: find and replace of same length
{
for(x=i,y=0;x<i+f;x++,y++)
{
src[x]=replace[y];
}
i=--x;// to start comparing starting from the character following the 'find' substring in src

}
else if(r<f)// case 2: find longer than replace
{
for(y=0;y<r;i++,y++)
{
src[i]=replace[y];
}


for(x=i,y=i+f-r;y<s;x++,y++)
src[x]=src[y];

src[x]='\0';
}

else// case 3: replace longer than find
{
strcpy(z,src);
for(x=i+r,y=i+f;y<s;x++,y++)
{
src[x]=z[y];
}
src[x]='\0';

for(y=0;y<r;y++,i++)
src[i]=replace[y];

s+=r-f;
}
}
}
return src;
}


int main()
{
char src[50],find[50],replace[50],*final;
char* findReplace(char*, char*,char*);

cout<<"\n Enter source ";
gets(src);

cout<<"\n Enter find ";
gets(find);

cout<<"\n Enter replace : ";
gets(replace);

final=findReplace(src,find,replace);
cout<<"\n "<<final;

return 0;
}

this code is simple and work even if len of replacement string is longer...
but its space complexity is O(n)
n i think its good to have this space complexity rather than moving the whole string in case replace ment string is longer....
#include<iostream>
using namespace std;
void searchNreplace(char *a,char *s,char *r,char *n);
int main()
{
char a[100],search[50],replace[50],newstr[100];
cout << "Enter the string\n";
cin.getline(a,100);
cout << "Enter the string to be searched\n";
cin.getline(search,50);
cout << "Enter the string to be replaced with\n";
cin.getline(replace,50);
searchNreplace(a,search,replace,newstr);
cout << newstr << endl;
system("pause");
return 0;
}
void searchNreplace(char *a,char *s,char *r,char *n)
{
int slen = strlen(s),i=0;
char *p = s;
char *m = r;
while(*a)
{
if(*a == *s)
{
char *z = a;
while(*a && *s)
{
if(*a == *s)
{
i++;
a++;
s++;
}
else
break;
}
if(i == slen)
{
s = p;
while(*r)
{
*n++ = *r++;
}
r=m;
}
else
{
*n++ = *z;
a=++z;
s = p;
}
i=0;
}
else
{
*n++ = *a++;
}
}
*n = '\0';
}

this code is simple and work even if len of replacement string is longer...
but its space complexity is O(n)
n i think its good to have this space complexity rather than moving the whole string in case replace ment string is longer....
#include<iostream>
using namespace std;
void searchNreplace(char *a,char *s,char *r,char *n);
int main()
{
char a[100],search[50],replace[50],newstr[100];
cout << "Enter the string\n";
cin.getline(a,100);
cout << "Enter the string to be searched\n";
cin.getline(search,50);
cout << "Enter the string to be replaced with\n";
cin.getline(replace,50);
searchNreplace(a,search,replace,newstr);
cout << newstr << endl;
system("pause");
return 0;
}
void searchNreplace(char *a,char *s,char *r,char *n)
{
int slen = strlen(s),i=0;
char *p = s;
char *m = r;
while(*a)
{
if(*a == *s)
{
char *z = a;
while(*a && *s)
{
if(*a == *s)
{
i++;
a++;
s++;
}
else
break;
}
if(i == slen)
{
s = p;
while(*r)
{
*n++ = *r++;
}
r=m;
}
else
{
*n++ = *z;
a=++z;
s = p;
}
i=0;
}
else
{
*n++ = *a++;
}
}
*n = '\0';
}

The logic of program is as follows:
Assume following pointers
Source – Pointing to original string
Search – Pointing to sub-string to be searched
Replace – Pointing to replacement string
Result – Pointing to Resultant
Temp – Temporary

We will be moving contents of Source & Replace (when Search Matches Substring in Source)
Into Result

Temp is basically used to keep track of how many characters of substring in Source matches with Search String.

Think of problem in this way:
Source - shiiine
Search - iin
Replace - abc

Expected Result – shiabce

1. Start moving contents of Source -> Result (as long as nothing is similar to Search)
i.e. sh -> Result

2. Now, ‘i’ onwards comparison of search substring will start. ‘ii’ in Source = ‘ii’ in Search
(This is fine… But don’t start replacing as all the characters are to be compared yet…)
Another thing: When comparison starts with first equal character save the address of source in Temp. (I.e. in this case save Source[2] address in Temp as ‘i’ in Source = ‘i’ in Search)

3. In the next iteration, is the main problem?
What should we do when we encounter ‘i’ (i.e. Source[4]) != ‘n’ in Search (i.e. Search[2])\

As, we have encountered first mismatching character, so
move Temp[0] -> Result (i.e. ‘i’ which is actually Source[2] will go to Result),
Make Source point to Temp[1] which is actually Source[3],
Make Search point to Search[0] and start over the comparison

4. When we find matching characters of equal length,
move Replace -> Result and
increment Source Pointer as usual.

Source Code: Same as previous posting, but with good readability

void searchNreplace(char *strSource,char *strSearch,char *strReplace,char *strResult)
{
    int iLength = strlen(strSearch);
    int iIndex = 0;
    char *pszSearch  = strSearch;
    char *pszReplace = strReplace;

    while(*strSource)
    {
        if(*strSource == *strSearch)
        {
            char *strTemp = strSource;

            /*Compare Source with Search Substring*/
            while(*strSource && *strSearch)
            {
                if(*strSource == *strSearch)
                {
                    iIndex++;
                    strSource++;
                    strSearch++;
                }
                else
                {
                    break;
                }
            }
            
            /*If the length of comparison is same*/
            if(iIndex == iLength)
            {
                strSearch = pszSearch;
                while(*strReplace)
                {
                    *strResult++ = *strReplace++;
                }
                strReplace=pszReplace;
            }
            /*If the length of comparison is not same i.e. difference is of 1 character*/
            else
            {
                /*Move first character of Temp, make Source point to next character of Temp and Start over Search substring*/
                *strResult++ = *strTemp;
                strSource    = ++strTemp;
                strSearch    = pszSearch;
            }
            iIndex = 0;
        }
        else
        {
            *strResult++ = *strSource++;
        }
    }
    *strResult = '\0';
}