1 ///page71 2 ///测试样例：nihao 3 ///output 4 /*5 5 5 nihao 6 0 7 10 nihaonihao 8 4 aoni 9 4 10 14 nihaoaoninihao 11 9 noninihao 12 13 nombxzmbxzhao*/ 13 #include <stdio.h> 14 #include <stdlib.h> 15 #include<string.h> 16 #include <malloc.h> 17 #define TRUE 1 18 #define FALSE 0 19 #define OK 1 20 #define ERROR 0 21 #define INFEASIBLE -1 22 #define OVERFLOW -2 23 #define maxlen 255 24 typedef char sstring[maxlen+1]; 25 typedef int status; 26 int StrLength(sstring s){ 27 int cnt=0; 28 for(int i=0;s[i];i++) 29 cnt++; 30 return cnt; 31 } 32 status StrAssign(sstring &t,char *chars){ 33 if(StrLength(chars)>maxlen) 34 return ERROR; 35 t[0]=StrLength(chars); 36 for(int i=1;i<=t[0];i++) 37 t[i]=*(chars+i-1); 38 t[t[0]+1]=' '; 39 } 40 void clears(sstring &s){ 41 s[0]=0; 42 } 43 void StrCopy(sstring &s,sstring t){// 由串S复制得串T 44 int i; 45 for(i=0;i<=t[0];i++) 46 s[i]=t[i]; 47 s[s[0]+1]=' '; 48 } 49 status StrEmpty(sstring s){// 若S为空串，则返回TRUE，否则返回FALSE 50 if(s[0]==0) 51 return TRUE; 52 else 53 return FALSE; 54 } 55 int StrCompare(sstring s,sstring t){// 初始条件：串S和T存在。操作结果：若S>T，则返回值>0； 56 //若S=T，则返回值=0；若S<T，则返回值<0 57 int i; 58 for(i=1;i<=s[0]&&i<=t[0];++i) 59 if(s[i]!=t[i]) 60 return s[i]-t[i]; 61 return s[0]-t[0]; 62 } 63 status concat(sstring &t,sstring s1,sstring s2){ 64 if(s1[0]+s2[0]<=maxlen){ 65 for(int i=1;i<=s1[0];i++) 66 t[i]=s1[i]; 67 for(int i=1;i<=s2[0];i++) 68 t[i+s1[0]]=s2[i]; 69 t[0]=s1[0]+s2[0]; 70 t[t[0]+1]=' '; 71 } 72 else if(s1[0]<maxlen){ 73 for(int i=1;i<=s1[0];i++) 74 t[i]=s1[i]; 75 for(int i=1;i<=maxlen-s1[0];i++) 76 t[i+s1[0]]=s2[i]; 77 t[0]=maxlen; 78 } 79 else{ 80 for(int i=1;i<=maxlen;i++) 81 t[i]=s1[i]; 82 t[0]=maxlen; 83 } 84 } 85 status SubString(sstring &Sub,sstring S,int pos,int len)// 用Sub返回串S的第pos个字符起长度为len的子串。 86 { 87 int i; 88 if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1) 89 return ERROR; 90 for(i=1;i<=len;i++) 91 Sub[i]=S[pos+i-1]; 92 Sub[0]=len; 93 Sub[len+1]=' '; 94 return OK; 95 } 96 int Index(sstring S,sstring T,int pos){// 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 97 int i,j; 98 if(1<=pos&&pos<=S[0]){ 99 i=pos; 100 j=1; 101 while(i<=S[0]&&j<=T[0]){ 102 if(S[i]==T[j]) // 继续比较后继字符 103 { 104 ++i; 105 ++j; 106 } 107 else // 指针后退重新开始匹配 108 { 109 i=i-j+2; 110 j=1; 111 } 112 } 113 if(j>T[0]) 114 return i-T[0]; 115 else 116 return 0; 117 } 118 else 119 return 0; 120 } 121 status StrInsert(sstring &S,int pos,sstring T){// 在串S的第pos个字符之前插入串T。 122 int i; //完全插入返回TRUE，部分插入返回FALSE 123 if(pos<1||pos>S[0]+1) 124 return ERROR; 125 if(S[0]+T[0]<=maxlen){ // 完全插入 126 for(i=S[0];i>=pos;i--) 127 S[i+T[0]]=S[i]; 128 for(i=pos;i<pos+T[0];i++) 129 S[i]=T[i-pos+1]; 130 S[0]+=T[0]; 131 S[S[0]+1]=' '; 132 return TRUE; 133 } 134 else{ // 部分插入 135 for(i=maxlen;i>=pos+T[0];i--) 136 S[i]=S[i-T[0]]; 137 for(i=pos;i<pos+T[0]&&i<=maxlen;i++) 138 S[i]=T[i-pos+1]; 139 S[0]=maxlen; 140 141 return FALSE; 142 } 143 } 144 status StrDelete(sstring &S,int pos,int len){//从串S中删除第pos个字符起长度为len的子串 145 int i; 146 if(pos<1||pos>S[0]-len+1||len<0) 147 return ERROR; 148 for(i=pos+len;i<=S[0];i++) 149 S[i-len]=S[i]; 150 S[0]-=len; 151 S[S[0]+1]=' '; 152 return OK; 153 } 154 155 status Replace(sstring &S,sstring T,sstring V) // 用V替换主串S中出现的所有与T相等的不重叠的子串 156 { 157 int i=1; // 从串S的第一个字符起查找串T 158 status k; 159 if(StrEmpty(T)) // T是空串 160 return ERROR; 161 do 162 { 163 i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置 164 if(i) // 串S中存在串T 165 { 166 StrDelete(S,i,T[0]); // 删除该串T 167 k=StrInsert(S,i,V); // 在原串T的位置插入串V 168 if(!k) // 不能完全插入 169 return ERROR; 170 i+=V[0]; // 在插入的串V后面继续查找串T 171 } 172 }while(i); 173 S[S[0]+1]=' '; 174 return OK; 175 } 176 177 int main(){ 178 sstring s,t,in; 179 scanf("%s",in); 180 //scanf("%s",t); 181 StrAssign(t,in); 182 printf("%d ",t[0]); 183 184 StrCopy(s,t); 185 printf("%d %s ",s[0],s+1); 186 187 printf("%d ",StrCompare(s,t)); 188 189 sstring all; 190 concat(all,s,t); 191 printf("%d %s ",all[0],all+1); 192 193 sstring sub; 194 SubString(sub,all,4,4); 195 printf("%d %s ",sub[0],sub+1); 196 197 int locate=Index(all,sub,2); 198 printf("%d ",locate); 199 200 StrInsert(all,6,sub); 201 printf("%d %s ",all[0],all+1); 202 203 StrDelete(all,2,5); 204 printf("%d %s ",all[0],all+1); 205 206 sstring s1,s2; 207 s1[0]=2; 208 s1[1]='n',s1[2]='i',s1[3]=' '; 209 s2[0]=4,s2[1]='m',s2[2]='b',s2[3]='x',s2[4]='z',s2[5]=' '; 210 Replace(all,s1,s2); 211 printf("%d %s ",all[0],all+1); 212 return 0; 213 }