题目：.编写算法实现串的置换操作Replace( S, T, R), 即将串S中所有与串T相等的子串置换为串R。

实现代码：

#include<iostream>
#include <stdio.h>
using namespace std;
#define MaxSize 100
typedef struct
{	char data[MaxSize];int length;			//串长
} SqString;void StrAssign(SqString &s, char cstr[])	//字符串常量赋给串s
{	int i;for (i = 0; cstr[i] != '\0'; i++)s.data[i] = cstr[i];s.length = i;
}void DestroyStr(SqString &s)
{  }void StrCopy(SqString &s, SqString t)	//串复制
{	int i;for (i = 0; i < t.length; i++)s.data[i] = t.data[i];s.length = t.length;
}bool StrEqual(SqString s, SqString t)	//判串相等
{	bool same = true;int i;if (s.length != t.length)				//长度不相等时返回0same = false;elsefor (i = 0; i < s.length; i++)if (s.data[i] != t.data[i])	//有一个对应字符不相同时返回0{	same = false;break;}return same;
}int StrLength(SqString s)	//求串长
{	return s.length;
}SqString Concat(SqString s, SqString t)	//串连接
{	SqString str;int i;str.length = s.length + t.length;for (i = 0; i < s.length; i++)	//将s.data[0..s.length-1]复制到strstr.data[i] = s.data[i];for (i = 0; i < t.length; i++)	//将t.data[0..t.length-1]复制到strstr.data[s.length + i] = t.data[i];return str;
}SqString SubStr(SqString s, int i, int j)	//求子串
{	SqString str;int k;str.length = 0;if (i <= 0 || i > s.length || j < 0 || i + j - 1 > s.length)return str;					//参数不正确时返回空串for (k = i - 1; k < i + j - 1; k++)  		//将s.data[i..i+j]复制到strstr.data[k - i + 1] = s.data[k];str.length = j;return str;
}SqString InsStr(SqString s1, int i, SqString s2)	//插入串
{	int j;SqString str;str.length = 0;if (i <= 0 || i > s1.length + 1) //参数不正确时返回空串return str;for (j = 0; j < i - 1; j++)      		//将s1.data[0..i-2]复制到strstr.data[j] = s1.data[j];for (j = 0; j < s2.length; j++)		//将s2.data[0..s2.length-1]复制到strstr.data[i + j - 1] = s2.data[j];for (j = i - 1; j < s1.length; j++)		//将s1.data[i-1..s1.length-1]复制到strstr.data[s2.length + j] = s1.data[j];str.length = s1.length + s2.length;return str;
}SqString DelStr(SqString s, int i, int j)		//串删去
{	int k;SqString str;str.length = 0;if (i <= 0 || i > s.length || i + j > s.length + 1) //参数不正确时返回空串return str;for (k = 0; k < i - 1; k++)       		//将s.data[0..i-2]复制到strstr.data[k] = s.data[k];for (k = i + j - 1; k < s.length; k++)	//将s.data[i+j-1..s.length-1]复制到strstr.data[k - j] = s.data[k];str.length = s.length - j;return str;
}SqString RepStr(SqString s, int i, int j, SqString t)	//子串替换
{	int k;SqString str;str.length = 0;if (i <= 0 || i > s.length || i + j - 1 > s.length) //参数不正确时返回空串return str;for (k = 0; k < i - 1; k++)				//将s.data[0..i-2]复制到strstr.data[k] = s.data[k];for (k = 0; k < t.length; k++)   		//将t.data[0..t.length-1]复制到strstr.data[i + k - 1] = t.data[k];for (k = i + j - 1; k < s.length; k++)	//将s.data[i+j-1..s.length-1]复制到strstr.data[t.length + k - j] = s.data[k];str.length = s.length - j + t.length;return str;
}void DispStr(SqString s)	//输出串s
{	int i;if (s.length > 0){	for (i = 0; i < s.length; i++)printf("%c", s.data[i]);printf("\n");}
}void Getbiaohaoxiazhi(SqString t, int nextval[])
{	int j = 0, k = -1;nextval[0] = -1;while (j < t.length){	if (k == -1 || t.data[j] == t.data[k]){	j++;k++;if (t.data[j] != t.data[k])nextval[j] = k;elsenextval[j] = nextval[k];}elsek = nextval[k];}
}int KMPIndex1(SqString s, SqString t)
{	int nextval[MaxSize], i = 0, j = 0;Getbiaohaoxiazhi(t, nextval);while (i < s.length && j < t.length){	if (j == -1 || s.data[i] == t.data[j]){	i++;j++;}elsej = nextval[j];}if (j >= t.length)return (i - t.length);elsereturn -1;
}SqString Repalce(SqString S, SqString T, SqString R)
{	int i, flag = 1; //用于保存与串T相等的S串的下标起始值SqString str, str1; //str 返回值;str1 变动串str.length = 0;StrCopy(str1, S); //在str1上进行改动while (flag){	i = KMPIndex1(str1, T);if (i == -1){	flag = 0;break;//串S中没有与T相等的子串，退出}str = Concat(str, SubStr(str1, 1, i)); //第一次时将str1之前的字符连接在str上;第一次以后因为有修改str1.str = Concat(str, R); //连接替换内容StrCopy(str1, SubStr(str1, i + T.length + 1, str1.length - (i + T.length))); //将i+T.length之前的字符删去}str = Concat(str, str1); //循环中找不到等于T的子串后，将剩下的str1加到str尾部return str;
}int main()
{	SqString S, T, R;char s[] = "我拿红豆比作友情，你拿红豆比作爱情。";char t[] = "红豆";char r[] = "长亭";StrAssign(S, s);StrAssign(T, t);StrAssign(R, r);SqString str;printf("串S:");DispStr(S);printf("串T:");DispStr(T);printf("串R:");	DispStr(R);str = Repalce(S, T, R);printf("替换后:");	DispStr(str);return 0;
}