一道笔试题 - strrep()函数的实现

来自http://www.cppblog.com/qinzuoyan/archive/2010/06/10/117548.html

实现这个函数：
char* strrep(const char* src,  const char* from, const char* to)
{
}

将src中出现的所有from替换成to
时间：
10分钟。

要求：
1. 功能正确，尽量高效
2.不能调用现有的正则表达式库
3.可以使用strdup，malloc，realloc等函数，以及其他的c字符串 操作函数
4.估算你所写算法的时间复杂度

#include <string.h>
#include <malloc.h>

/**
 * On success, strrep() returns a newly allocated string, which is constructed by replacing all substring `from' in `src' with `to'.
 * If `from' is a null string(with length of 1), then return a duplication of `src'.
 *
 * On failure
 *   ENOMEM Insufficient memory is available.
 * 
 * src is a null-terminated string.
 * from is a null-terminated string.
 * to is a null-terminated string.
 * 
 */
char* strrep(const char* src,  const char* from, const char* to)
{
  char *des, *des_cur;
  int from_len, to_len, src_len, des_len;
  const char *src_cur, *src_end, *occ;
  const char **marks; 
  int mark_len, m, rep_count;
  // prepare
  from_len = strlen(from);
  to_len = strlen(to);
  src_len = strlen(src);
  if (from_len == 0)
    return strdup(src);
  // mark all occurence of `from' in `src'
  mark_len = 0x4;
  marks = (const char**)malloc(sizeof(char*) * mark_len);
  if (marks == NULL)
    return NULL;
  rep_count = 0;
  src_cur = src;
  while((occ = strstr(src_cur, from)) != NULL) {
    rep_count++;
    // need more space for mark
    if (rep_count > mark_len) {
      mark_len << 1;
      marks = (const char**)realloc(marks, mark_len);
      if (marks == NULL)
        return NULL;
    }
    // mark the position
    marks[rep_count - 1] = occ;
    // find next occurence from the current position
    src_cur = occ + from_len;
  }
  // construct new string
  des_len = src_len + (to_len - from_len) * rep_count;
  des = (char*)malloc(des_len + 1);
  if (des == NULL)
    return NULL;
  des_cur = des;
  src_cur = src;
  m = 0;
  if (m < rep_count)
    occ = marks[m];
  else
    occ = NULL;
  while(*src_cur) {
    if (src_cur != occ)
      *des_cur++ = *src_cur++;
    else {
      // replace `from' with `to'
      strncpy(des_cur, to, to_len);
      src_cur += from_len;
      des_cur += to_len;
      // more to replace?
      m++;
      if (m < rep_count)
        occ = marks[m];
      else
        occ = NULL;
    }
  }
  des_cur = '\0';
  free(marks);
  return des;
}