CareerCup

1) find the starting index of substring
a) can be done by KMP in O(n)
b) brute force O(n*m)

2) replacing
a) if the word to be replaced is larger-- then first replace the characters till the length of substring..then use shifting so--> O((l1-l2)*n)
b) if the word to be replaced is small
then just replace snd shift

when you are doing the shifting you will end up loosing trailing characters. How you are going to deal with that?

I think we can just assume the target array have enough memory after '\0'
because every replace string work like that or make error

I made some but it is not KMP or something efficient algorithm but it is easy to write front of interviewer.

int main(int argc, char *argv[])
{

int idx = 0;
char target[100];
char *pTag = target;
char sub[10];
char replace[100];
char *pRpr = replace;
if(argc != 4)
{
cout << "Exit... Bye Bye\n";
exit(1);
}

strcpy(target, argv[1]);
strcpy(sub,argv[2]);
strcpy(replace,argv[3]);

//Loop until target 0
char * pTg, * pSb, *pRp;
pRp = replace;
while(pTag != '\0')
{
pTg = pTag;
pSb = sub;
while(*pSb != '\0' && *pTg != '\0' && *pTg++ == *pSb++);
if(*pSb == '\0' && *(pTg -1) == *(pSb -1))
{
while(*pRp != '\0')pRp++;
while((*pRp++ = *pTg++) != '\0');
while((*pTag++ = *pRpr++) != '\0');
cout << target << "\n";
return 0;
}
pTag++;
}
}

#include<iostream>
using namespace std;

void replace(char *target, char *substring, char *replace);



int main()
{
char target[100] = "MyNameIsGajanan";
char *substring = "Gajan", *rep = "AAA";
//cout << target <<substring <<replace <<endl;
replace(target,substring,rep);
return 0;
}

void replace(char *target, char *substring, char *rep)
{
char *occur, temp[100]="";

occur = strstr(target,substring);
cout << occur <<endl;

int lensubstring = strlen(substring);
int lenrep = strlen(rep);
strcpy(temp,occur+lensubstring);

strcpy(occur,rep);
strcpy(occur+lenrep,temp);
cout<<"The output is = "<<target <<endl;
return;
}


The output is = MyNameIsAAAan

#include <stdio.h>
#include <string.h>

int main ()
{
char *target;
char *pch;
pch = strstr (target,substring);
strncpy (pch,replacement,sizeof(replacement));
puts (target);
return 0;
}

Algo also need to support for replacement of mulitiple occurance of substring with replacement string.

Thx.
Venkatesh.

we can use c++ STL's in-built functions
1: find_first_of(substring). this will give us the index where substring starts
2: copy target string till that point in some other string
3: append the replacement to this string
4: starting index of replacement + sizeof(substring) will give starting index of remainder of starting string
5: append that much to the new string

i am making use of C++ STL inbuilt functions, don't know if its allowed.

OK, enjoy this code. ;) I just implemented helper StrStr function (in the case if we're not allowed to use any string library function)

char* StrStr(char* str, char* strSearch)
{
    char* strResult = NULL;
    if (str && strSearch)
    {
        char *s1 = NULL, *s2 = NULL;
        while (*str && *strSearch)
        {
            s1 = str;
            s2 = strSearch;

            while (*str && *strSearch)
            {
                if (*str != *strSearch)
                {
                    str = s1;
                    strSearch = s2;
                    break;
                }
                str++;
                strSearch++;
            }

            if (!*strSearch)
            {
                strResult = s1;
                break;
            }
            str++;
        }
    }
    return strResult;
}

//
// we assume strTarget have enough space if need to be expanded
//
char* Replace(char* strTarget, char* strSubstr, char* strReplacement)
{
    char *strResult = NULL;
    if (strTarget && strSubstr && strReplacement)
    {
        char *tempSubstr = strSubstr;
        char *tempReplacement = strReplacement;
        char *strEnd = strTarget;
        while (*strEnd)
        {
            strEnd++;
        }
        char *strNewEnd = strEnd;
        
        char *strFound = StrStr(strTarget, strSubstr);
        strResult = strFound;

        while (strFound)
        {
            strTarget = strFound;
            tempSubstr = strSubstr;
            tempReplacement = strReplacement;
            for (;*tempReplacement && *strTarget == *tempSubstr; strTarget++, tempSubstr++)
            {
                *strTarget = *tempReplacement++;
            }

            //
            // handle the situation if substring longer than replacement
            //
            if (*strTarget == *tempSubstr)
            {
                char *strCurrent = strTarget;
                //
                // pass the rest of the substring
                //
                for (;*strTarget == *tempSubstr; strTarget++, tempSubstr++);

                //
                // left shift the rest of the string after replacement
                //
                strEnd = strTarget;
                for (;*strEnd; strCurrent++, strEnd++)
                {
                    *strCurrent = *strEnd;
                }
                *strCurrent = '\0';
                strEnd = strNewEnd = strCurrent;
            }
            else
            {
                //
                // handle the situation if substring shorter than replacement
                //
                if (*tempReplacement)
                {
                    //
                    // right shift the string
                    //
                    unsigned int uDiff = strEnd-strTarget;
                    *(strEnd+1) = '\0';
                    strNewEnd = strEnd+1;
                    for (;uDiff > 0; uDiff--, strEnd--)
                    {
                        *(strEnd+1) = *strEnd;
                    }
                    *(strEnd+1) = *strEnd;
                    strEnd = strNewEnd;

                    //
                    // copy the rest of replacement
                    //
                    for (;*tempReplacement; strTarget++, tempReplacement++)
                    {
                        *strTarget = *tempReplacement;
                    }
                }
            }

            strFound = StrStr(strTarget, strSubstr);
        }
    }

    return strResult;

}