每日一练算法题（堆串的基本操作StrReplace(S, T, V)）

6-2 堆串的基本操作StrReplace(S, T, V)

编写算法，实现堆串的基本操作StrReplace(S, T, V)。

初始条件: 串S, T和 V 均已存在,且 V 是非空串。

操作结果: 用V替换主串S中出现的所有与(模式串)T相等的不重叠的子串。
输入格式:

第一行：S

第二行：T

第三行：V

输出格式:

S = 被替换后的结果

函数接口定义：

void StrReplace(HString *S, HString T, HString V);

堆串类型定义如下：

typedef struct
{char *ch;int  len;
}HString;

裁判测试程序样例：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct{char *ch;int  len;
}HString;void StrReplace(HString *S, HString T, HString V);/*串初始化函数*/
void StrInit(HString *s)
{s->ch=NULL;s->len=0;
}/*串赋值函数：将字符串常量tval的值赋给串s */
int StrAssign(HString *s, char *tval)
{    int len,i=0;if (s->ch!=NULL) free(s->ch);while (tval[i]!='\0')  i++;len=i;if (len){s->ch=(char *)malloc(len);if (s->ch==NULL)  return(0); for (i=0;i<len;i++)s->ch[i]=tval[i];}else  s->ch=NULL;s->len=len;return(1);
}/*串插入函数：在串s中下标为pos的字符之前插入串t */
int StrInsert(HString *s, int  pos, HString t){int i;  char *temp;if (pos<0 || pos>s->len || s->len==0)return(0);temp=(char *)malloc(s->len + t.len);if (temp==NULL)  return(0);for (i=0;i<pos;i++)temp[i]=s->ch[i];for (i=0;i<t.len;i++)temp[i+pos]=t.ch[i];for (i=pos;i<s->len;i++)temp[i + t.len]=s->ch[i];s->len+=t.len;free(s->ch);s->ch=temp;return(1);
} /*串删除函数：在串s中删除从下标pos起len个字符 */
int StrDelete(HString *s, int pos, int len) {int i; char *temp;if (pos<0 || pos>(s->len - len))return(0);temp=(char *)malloc(s->len - len);if (temp==NULL)  return(0);for (i=0;i<pos;i++)temp[i]=s->ch[i];for (i=pos;i<s->len - len;i++)temp[i]=s->ch[i+len];s->len=s->len-len;free(s->ch);s->ch=temp;return(1);
}/*串的简单模式匹配：求串t在串s中的位置*/
int StrIndex(HString *s, int pos, HString t){int i,j,start;if (t.len==0)  return(0);start=pos; i=start; j=0;while (i<s->len && j<t.len){if (s->ch[i]==t.ch[j])  {i++;j++;}else  {start++; i=start; j=0;}}if (j>=t.len) return(start);else return(-1);
} void main()
{HString s, t, v;char str1[100],str2[100],str3[100];int i;gets(str1);  StrInit(&s);  StrAssign(&s, str1);gets(str2);  StrInit(&t);  StrAssign(&t, str2);gets(str3);  StrInit(&v);  StrAssign(&v, str3);StrReplace(&s, t, v);printf("S = '");for(i=0;i<s.len;i++)printf("%c", s.ch[i]);printf("'\n");
}/* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

abcaabcaaabca
bca
x

输出样例：

在这里给出相应的输出。例如：

S = 'axaxaax'

void StrReplace(HString *S,HString T,HString V){int index=0;while((index=StrIndex(S,index,T))!=-1){StrDelete(S,index,T.len);StrInsert(S,index,V);index+=V.len;}
}