笔试题82.新浪微博算法题

    这是我在面试过程中遇到的一道代码算法题，需要我在一定的时间内完成这个题目， 题目的描述：

                将某字符串str1中的字符串str2，全部替换成字符串str3。
                例如：str1=”abcecbbccefgxyzbcgbcg”，
str2=”bc”,
str3=”xy”.
替换后为”axyecbxycefgxyzxygxyg”
        请尽可能考虑各类情况，并保证时间复杂度和空间复杂度最优。

    这个题看似简单的做法是可以的解决的，我当时也想过简单的暴力求解法解决。后来我仔细想了想，这个题目应该分为三步：

1找，2定，3换。先找到服药要求的串，找出它的下标，替换该字符串。

    我们都知道字符串的查找算法中最有名的就是KMP算法了，所以我决定采用KMP算法去找，找到下标后就可以替换了。若是不懂KMP算法的话，我建议大家去七月的博客上看一下他写的详解KMP算法，写的很详细很清晰很容易上手。我这里主要是解决这个题，先就不说KMP算法的原理和部件了。我们主要讨论解题的方法，下面我就给出代码，可能并不是最优的解法，大家若有更好的解法记得跟我交流一下，一起分享一下。

//构造next 数组 
void makeNext(const char *patten,int *arr) 
{ 
	assert(patten); 
	int len = strlen(patten); 
	int pos1 = 1; 
	int pos2 = 0; 
	for(inti = 1; i<len; i++) 
	{ 
	   if(pos1 <= i && patten[pos1-1] == patten[pos2]) 
	   {
		arr[i]=arr[i-1]+1; //若前面已经出现了前缀后缀匹配，则 next 值加一 pos2++;
	   } 
	   else 
	   {
		if(patten[pos1-1]==patten[0])//前面的匹配失败，可能存在新的前缀后缀匹配
		{
			arr[i]=1; 
			pos2=1;
		}
	   } 
	   ++pos1;
	}
	
	for(inti = len-1; i>0; --i) 
        { 
	    arr[i]=arr[i]-1; 
	} 
	arr[0]=-1;
}

//将配位位置的模式串替换成新串 
void Replace(char *str,const char *newstr,int plen) 
{ 
	assert(str); 
	assert(newstr); 
	for(inti = 0; i < plen; ++i) 
	{
	    str[i] = newstr[i]; 
	} 
}	

//查找匹配的串的位置 
int Find(const char *str,const char *patten,int len,const int *next) 
{ 
	assert(str); 
	assert(patten); 
	assert(next);
	intslen = strlen(str); //主串长度 
	if(slen == 1) //长度为 1 的字符串，相当于查找单个字符 
	{ 
		for(int i = 0; i < len; ++i)
		{
			if(str[i] == patten[0]) 
				return i;
		}
		return-1;
	}
	int s = 0; // 主串下标 
	int t = 0; // 子串下标 
	while(t<len && s<slen) 
	{ 
		if(str[s] == patten[t]) 
		{ 
			if(t == len-1)//成功匹配 
			{ 
				return(s-t); 
			} 
			++s; 
			++t; 
		 } 
		else//不相等 
		{ 
			if(next[t] == -1) //第一个都不匹配，子串与主串失败的下一个位置比较 
			{ 
				++s; 
				t = 0; 
				continue; 
			}
			t = next[t]; //前面的已经匹配，不用再比较了
		}
	} 
	return -1;
}

void ReplaceSubstr(char *str,const char *patten,const char *newstr) 
{ /* 目标：将 str中所有的 patten 串换成 newstr 串 */
	//判断指针是否合法 
	assert(str); 
	assert(patten);
	assert(newstr); 
	assert(strlen(patten) == strlen(newstr));
	//构造 next 数组 
	int plen = strlen(patten);//patten串的长度 
	int *next = newint[plen]; 
	memset(next,0,sizeof(int)*plen); 
	makeNext(patten,next);
	int slen = strlen(str);//主串的长度 char*pstr=str; //pstr 要不断往前移动
	int curpos = 0;//本次的相对偏移
	while( (curpos = Find(pstr,patten,plen,next) ) != -1) 
	{ 
		Replace(pstr+curpos,newstr,plen); 
		curpos += plen; 
		pstr += curpos; 
	}
	delete[]next;
}

//测试用例 
void TestReplacestr() 
{ /*charstr[]="abcecbbccefgxyzbcgbcg"; char*patten="bc"; char*newstr="xy";*/
	charstr[] = "abcecbbccefgxyzbcgb"; 
	char*patten = "b"; 
	char*newstr = "x"; 
	cout<<str<<endl; 
	ReplaceSubstr(str,patten,newstr); 
	cout<<str<<endl;
}

原文：http://blog.csdn.net/zr1076311296/article/details/51804696