qinzuoyan

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

常用链接

留言簿(3)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

实现这个函数:
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;
}


posted on 2010-06-10 12:16 左言 阅读(2338) 评论(1)  编辑 收藏 引用

Feedback

# re: 一道笔试题 - strrep()函数的实现[未登录] 2010-06-11 10:58 expter
KMp不就行了吗?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理