CareerCup

can u explain this question lill bit more

for given string
"fasdkfhawhasdrhasdfasdbygyasgfadfsdkfwerhasdfhkshfwf" find pattern "asd" replace with ","

$str ~= s/asd/,/g

I think it should look something like this:

void substitute(char str[], char const * const pattern, char const * const replace_with) {
    if(str == NULL || pattern == NULL || replace_with == NULL) {
        cerr << "bad arguments" << endl;
        exit(1);
    }

    char const *pattern_temp = pattern, *repl_with_temp = replace_with;
    while(*pattern_temp && *repl_with_temp) {
        ++pattern_temp; ++repl_with_temp;
    }
    if(!*pattern_temp && *repl_with_temp) {
        cerr << "pattern is smaller than replacement - insufficient memory space in string" << endl;
        exit(1);
    }

    char *str_replace = str;

    while(*str) {
        char const *pat = pattern;
        char const *repl_with = replace_with;
        
        if(*str == *pat) {
            // first symbol of pattern found in string
            size_t count = 0;
            while(*str && *pat && *str == *pat) {
                ++str; ++pat; ++count;
            }
            if(!*pat) {
                // whole substring found
                while(*repl_with) {
                    *str_replace++ = *repl_with++;
                }
            } else {
                // otherwise, move symbols skipped when checking back to the string
                while(count > 0) {
                    *(str_replace++) = *(str - (count--));
                }
            }
        } else {
            // if str_replace is already below str, then copy str to the new string
            if(str_replace != str) {
                *str_replace = *str;
            }
            ++str_replace;
            ++str;
        }
    }
    *str_replace = '\0';
}

Hope this is clear. If you replace the string parameters with char arrays, i guess this code will turn out to be an inplace algorithm.

Any comments are much appreciated.

public static void findPattern(string str, string pattern, string replacewith)
        {
            if (string.IsNullOrEmpty(str))
            { return; }

            char[] chr = str.ToCharArray();
            char[] ptrn = pattern.ToCharArray();
            char[] dest = replacewith.ToCharArray();

            int i=0, j=0, current=0;
            while (current < chr.Length - 1)
            {
                if (chr[i] != ptrn[j])
                {
                    chr[current++] = chr[i++];
                    j = 0;
                }
                else
                {
                    if (j == ptrn.Length - 1)
                    {
                        while (j >= 0)
                        {
                            chr[current + j] = dest[j--]; 
                        }

                        current += ptrn.Length;
                    }
                    j++;
                    i++;
                }
            }
        }
    }

Hope this is clear. If you replace the string parameters with char arrays, i guess this code will turn out to be an inplace algorithm.

Any comments are much appreciated.

public static void findPattern(string str, string pattern, string replacewith)
        {
            if (string.IsNullOrEmpty(str))
            { return; }

            char[] chr = str.ToCharArray();
            char[] ptrn = pattern.ToCharArray();
            char[] dest = replacewith.ToCharArray();

            int i=0, j=0, current=0;
            while (current < chr.Length - 1)
            {
                if (chr[i] != ptrn[j])
                {
                    chr[current++] = chr[i++];
                    j = 0;
                }
                else
                {
                    if (j == ptrn.Length - 1)
                    {
                        while (j >= 0)
                        {
                            chr[current + j] = dest[j--]; 
                        }

                        current += ptrn.Length;
                    }
                    j++;
                    i++;
                }
            }
        }
    }

Let input = I
Let Find string = F
Let Replace string = R
Let n = I.Length
Let fn = F.Length
Let rn = R.Length
Use KMP to find each occurrence of F in I store in an array A
Loop through this array to ensure that distance between consecutive elements is greater than fn.
If for any element the distance is less, delete that element
Let no. of elements remainining in array = c
if(rn>fn)
{
allocate (rn-fn)*c extra bytes to input I
shift the original string so that it occupies the end of the array ( e.g. 0000ABCD )
}

take two variables i = 0, j = start of the shifted array ( 0 in case of no shift )

Repeat till j < n
{
if j is not present in A
{
a[i]=a[j]
increment i
increment j
}
else
{
insert R
increment i by rn
increment j by fn
}
}