The optimizer should eliminate most of the local variables. The tmp pointer is there to make sure strcpy doesn't have to walk the string to find the null. tmp points to the end of result after each call. (See Shlemiel the painter's algorithm for why strcpy can be annoying.)

// You must free the result if result is non-NULL.
char *str_replace(char *orig, char *rep, char *with) {
    char *result; // the return string
    char *ins;    // the next insert point
    char *tmp;    // varies
    int len_rep;  // length of rep (the string to remove)
    int len_with; // length of with (the string to replace rep with)
    int len_front; // distance between rep and end of last rep
    int count;    // number of replacements

    // sanity checks and initialization
    if (!orig || !rep)
        return NULL;
    len_rep = strlen(rep);
    if (len_rep == 0)
        return NULL; // empty rep causes infinite loop during count
    if (!with)
        with = "";
    len_with = strlen(with);

    // count the number of replacements needed
    ins = orig;
    for (count = 0; (tmp = strstr(ins, rep)); ++count) {
        ins = tmp + len_rep;
    }

    tmp = result = malloc(strlen(orig) + (len_with - len_rep) * count + 1);

    if (!result)
        return NULL;

    // first time through the loop, all the variable are set correctly
    // from here on,
    //    tmp points to the end of the result string
    //    ins points to the next occurrence of rep in orig
    //    orig points to the remainder of orig after "end of rep"
    while (count--) {
        ins = strstr(orig, rep);
        len_front = ins - orig;
        tmp = strncpy(tmp, orig, len_front) + len_front;
        tmp = strcpy(tmp, with) + len_with;
        orig += len_front + len_rep; // move to next "end of rep"
    }
    strcpy(tmp, orig);
    return result;
}

Replacing a substring with another is easy if both substrings have the same length:

• locate the position of the substring with strstr
• if it is present, use memcpy to overwrite it with the new substring.
• assigning the pointer with *strstr(m, "on") = "in"; is incorrect and should generate a compiler warning. You would avoid such mistakes with gcc -Wall -Werror.
• note however that you cannot modify a string literal, you need to define an initialized array of char so you can modify it.

Here is a corrected version:

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

int main(void) {
    char m[] = "cat on couch";
    char *p = strstr(m, "on");
    if (p != NULL) {
        memcpy(p, "in", 2);
    }
    printf("%s\n", m);
    return 0;
}

If the replacement is shorter, the code is a little more complicated:

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

int main(void) {
    char m[] = "cat is out roaming";
    char *p = strstr(m, "out");
    if (p != NULL) {
        memcpy(p, "in", 2);
        memmove(p + 2, p + 3, strlen(p + 3) + 1);
    }
    printf("%s\n", m);
    return 0;
}

In the generic case, it is even more complicated and the array must be large enough to accommodate for the length difference:

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

int main(void) {
    char m[30] = "cat is inside the barn";
    char *p = strstr(m, "inside");
    if (p != NULL) {
        memmove(p + 7, p + 6, strlen(p + 6) + 1);
        memcpy(p, "outside", 7);
    }
    printf("%s\n", m);
    return 0;
}

Here is a generic function that handles all cases:

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

char *strreplace(char *s, const char *s1, const char *s2) {
    char *p = strstr(s, s1);
    if (p != NULL) {
        size_t len1 = strlen(s1);
        size_t len2 = strlen(s2);
        if (len1 != len2)
            memmove(p + len2, p + len1, strlen(p + len1) + 1);
        memcpy(p, s2, len2);
    }
    return s;
}

int main(void) {
    char m[30] = "cat is inside the barn";

    printf("%s\n", m);
    printf("%s\n", strreplace(m, "inside", "in"));
    printf("%s\n", strreplace(m, "in", "on"));
    printf("%s\n", strreplace(m, "on", "outside"));
    return 0;
}

Simple solution found on google: http://www.linuxquestions.org/questions/programming-9/replace-a-substring-with-another-string-in-c-170076/

Edit: Taking your specification into account, I've edited the code in the link to this:

char *replace_str(char *str, char *orig, char *rep, int start)
{
  static char temp[4096];
  static char buffer[4096];
  char *p;

  strcpy(temp, str + start);

  if(!(p = strstr(temp, orig)))  // Is 'orig' even in 'temp'?
    return temp;

  strncpy(buffer, temp, p-temp); // Copy characters from 'temp' start to 'orig' str
  buffer[p-temp] = '\0';

  sprintf(buffer + (p - temp), "%s%s", rep, p + strlen(orig));
  sprintf(str + start, "%s", buffer);    

  return str;
}

The fast_strncat() is a good idea. The actual copying isn't efficient (though a good optimiser might recognise the pattern), but letting the caller know how much was copied helps avoid a program being Schlemiel the painter.

I don't like the name; it sounds too much like strncat(), which has very different behaviour. Perhaps len_strcpy() or something better conveys the functionality?

And instead of passing a pointer to result, it's generally better to return the result (either as a number of characters as here - though size_t is probably a better choice of type - or perhaps as a pointer to the new string end).

It's possible we don't need it though - see our use of memcpy in the next section.

The way we're using strstr() is very inefficient. We're traversing input a character at a time, repeating the same search until our position reaches the search result. Imagine this in human terms:

• "Run down the road to the first red house, and tell me where it is."
• It's not this one, so walk ahead to the next house.
• "Run down the road to the first red house, and tell me where it is."

Doesn't this sound a lot like Shlemiel's algorithm, that we worked so hard to avoid earlier?

We could consider using strncmp() instead in the same loop, but we can do better. Once we have the result from strstr(), we know there are no matches up to that result. So we can measure the length change much more simply:

size_t count_old = 0;
for (const char *p = *str;  (p = strstr(p, old));  ++p) {
    ++count_old;
}

And we can copy each chunk in one go:

while (*temp) {
    const char *next_match = strstr(temp, old);
    if (next_match) {
        size_t match_len = next_match - temp;
        memcpy(buff+i, temp, match_len);
        i += match_len;
        temp += match_len;
        memcpy(buff+i, new, len_n);
        i += len_n;
        temp += len_o;
    } else {
        /* no match - copy the remainder */
        strcpy(buff+i, temp);
    }

The code is quite limited because it will only work with seekable files, it has to read the entire file into memory, and it needs space for the entire output file in memory before it starts writing.

We can make it more efficient (and avoid the need to seek) by reading a buffer of characters, replacing matches within the buffer, and then writing out the buffer, before repeating. There's a small complication that we need to deal with matches that might straddle two reads - we need to write out all but len_o - 1 characters, and then move those last few to the front of the buffer, before reading the next characters after them. If we know we're working with streams, then there's no need to write to a new string array - just fwrite() each chunk as we get there.

On the other hand, if we want a general function to work on in-memory strings, we can avoid needing separate input and output arrays. It's possible to perform replacement in situ, provided our buffer is big enough to hold the bigger of input and output. The code needs to have two branches - working from the end if the replacement string is bigger than the match string, or from the beginning otherwise. I'd definitely recommend using unit tests to guide implementation if you choose to attempt such in-place substitution.

We have no error checking for the fwrite() and fclose() in main(). These functions can and do fail (e.g. disk quota reached), and we mustn't mislead the user that we succeeded if we haven't written all the output.

Minor things:

• We don't need to include a newline at the end of the message we give to perror(). That function will append : and error description, then a newline of its own.
• temp isn't a great name for a variable. It only tells us that it's short-lived, but doesn't indicate what it's for.
• There are many redundant casts - I don't think any of the casts here are necessary (Any Type* converts automatically to Type const* - a cast just costs the reader's time, and makes it harder to spot the true problems).
• The if (ptr) test leaves us holding state in our heads for half a screenful - it's easier to read if we test if (!ptr), which has a much shorter block (and also exits the function).
• sizeof (char) is always 1 (because sizeof works in units of char), so those expressions can be simplified.

One problem I can see is that if the replacement string contains the search string, you'll loop forever (until you run out of memory).

For example:

char *result = str_replace("abc", "a", "aa");

Also, doing another malloc/free every time you replace one instance is pretty expensive.

A better approach would be to do exactly 2 passes over the input string:

• the first pass, count how many instances of the search string are present

• now that you know how many matches, compute the length of your result & malloc once:

  strlen(string) + matches*(strlen(replacement)-strlen(substr)) + 1

• make a second pass through the source string, copying/replacing

It doesn't seem clear to me what algorithm you are trying to follow, it all looks fishy to me. What's probably the simplest approach is:

• search for first occurrence of the "needle" (searched-for substring)
• copy the part before the first occurrence to the result buffer
• append the replacement string to the result buffer
• increment the p pointer so it points just after the needle
• GOTO 10

void str_replace(char *target, const char *needle, const char *replacement)
{
    char buffer[1024] = { 0 };
    char *insert_point = &buffer[0];
    const char *tmp = target;
    size_t needle_len = strlen(needle);
    size_t repl_len = strlen(replacement);

    while (1) {
        const char *p = strstr(tmp, needle);

        // walked past last occurrence of needle; copy remaining part
        if (p == NULL) {
            strcpy(insert_point, tmp);
            break;
        }

        // copy part before needle
        memcpy(insert_point, tmp, p - tmp);
        insert_point += p - tmp;

        // copy replacement string
        memcpy(insert_point, replacement, repl_len);
        insert_point += repl_len;

        // adjust pointers, move on
        tmp = p + needle_len;
    }

    // write altered string back to target
    strcpy(target, buffer);
}

Warning: You also have to be careful about how you call your function. If the replacement string is larger than the needle, your modified string will be longer than the original one, so you have to make sure your original buffer is long enough to contain the modified string. E.g.:

char s[1024] = "marie has apples has";                         
str_replace(s, "has", "blabla");