replace.c

char *string_replace(const char *haystack, const char *needle, const char *replace) {
    char *out_str, *out_ptr;    // output string, pointer used for modifying output
    int out_len, replace_len;   // output length, replacement length
    const char *replace_iter, *haystack_iter;   // replacement iterater, haystack iterator
    const char *needle_iter = NULL;  // needle iterator
    const char *haystack_last; // last known position in the haystack, used for backtracking
    char haystack_val = 0; // last known value in the haystack (used to cut down on derefs)
    char needle_val = 0; // current value in the needle search
    
    if (!(haystack && needle && *haystack && *needle)) {
        // no usable haystack or needle = gtfo
        return NULL;
    }
    
    out_len = 0;
    out_str = out_ptr = NULL;
    replace_len = (replace ? strlen(replace) : 0);
    haystack_iter = haystack;
    
    // iterate through haystack string
    while ((haystack_val = *haystack_iter)) {
        // if there is no ongoing search and the first char of the needle matches
        // the current haystack value, begin a search
        if (!needle_iter && haystack_val == *needle) {
            // increment length/iterators since we already know about the first character
            needle_iter = needle+1;
            haystack_last = ++haystack_iter;
            ++out_len;
            continue;
        }
        
        // if there's an ongoing search
        if (needle_iter) {
            needle_val = *needle_iter;
            if (!needle_val) {
                // search complete, string matches the needle
                --out_len; // decrement length to account for the needle's length
                out_len += replace_len; // add the length of the replacement string to the output length
                needle_iter = NULL; // end the search
            } else if (needle_val == haystack_val) {
                // search is ongoing and still matching
                ++needle_iter;
                --out_len; // decrement length to account for the needle's length
            } else {
                // there was a non-matching character, terminate the search
                needle_iter = NULL;
                // backtrack to the last match
                haystack_iter = haystack_last;
            }
        }
        
        ++out_len;
        ++haystack_iter;
    }
    
    haystack_iter = haystack;
    out_ptr = out_str = (char*)malloc(out_len + 1 * sizeof(char));
    
    while ((haystack_val = *haystack_iter)) {
        if (!needle_iter && *haystack_iter == *needle) {
            needle_iter = needle+1;
            // we're now assigning characters to the output
            *out_ptr = haystack_val;
            haystack_last = ++haystack_iter;
            continue;
        }
        
        if (needle_iter) {
            if (!(needle_val = *needle_iter)) {
                // replacement matched
                replace_iter = replace;
                // iterate over the replacement, inserting its characters
                // into the output string
                while (*replace_iter)
                    *(out_ptr++) = *(replace_iter++);
                // end search
                needle_iter = NULL;
            } else if (needle_val == haystack_val) {
                // incrmeent needle search
                ++needle_iter;
            } else {
                // something didn't match, end the search
                needle_iter = NULL;
                ++out_ptr;
            }
        }
        
        if (!needle_iter) {
            // if no search is ongoing, add characters to the output string
            *(out_ptr++) = haystack_val;
        }
        
        // continue iterating through the haystack
        ++haystack_iter;
    }
    *out_ptr = '\0'; // null term
    
    return out_str;
}