主题：关于80次编程比赛，最终代码在底楼，谢谢版主帮测
Hawkxp [专家分：350] 发布于 2009-03-20 14:37:00
晚上我再重写代码,把要比较的字符串,开头有重复的字符先缩成一个字符再作比较,谢谢版主,晚上我再贴上来.
回想下线代的内容，对这题很有启发。
如果a中有一个字符比b的首字符大，那b串一定在该位置前插入，或者说，b串插入a的位置之前不能有比b首字符大的字符。。。
按这个思路考虑下去吧，你会发现这题居然是如此简单。
+++++++++++++++++++++++++++++++++++++++++++++++++
[color=FF00FF]代码已经重写过了,字典长度为4的测试文件完全通过,1楼的代码作废,当代码难以修改时,唯一的办法就是重写,请版主帮忙用100000长度的测试文件试试看,谢谢[/color]
最后更新于：2009-04-21 10:08:00
回复列表 （共23个回复）
21 楼
jiang5495 [专家分：0] 发布于 2009-03-28 21:45:00
不好意思,理解错误
22 楼
Hawkxp [专家分：350] 发布于 2009-03-31 16:32:00
重新整理后的代码,goto不是必要的,加一个变量就可去掉,但我觉得用了更容易看,保留
[code=c]
void deal(char* a, char* b, char* c)
{
// todo: 在此补充你的处理代码
// 参数说明: a和b是输入的字符串，c要保存输出结果
int i,j,k;
int Thead,Twidth,Tnum_a,Tnum_b;
int trend_a,trend_b,Tnum_compare;
i=0;
while(a[i]){
if(a[i]>b[0]) break;
else if(a[i]==b[0]){
Thead=i;Twidth=Tnum_a=Tnum_b=1;i++;
}else{i++;continue;}
cycle:
while(a[i] && a[i]==b[Twidth] && a[i]<b[0]){
Twidth++;i++;
}
j=trend_a=trend_b=Tnum_compare=0;
while(b[j%Twidth]==a[i+j])j++;
if(a[i+j]>b[j%Twidth])trend_a=2;
else if(a[i+j])trend_a=1;
Tnum_a+=j/Twidth;
j=0;
while(b[j%Twidth]==b[Twidth+j])j++;
if(b[Twidth+j]>b[j%Twidth])trend_b=2;
else if(b[Twidth+j])trend_b=1;
Tnum_b+=j/Twidth;
if(Tnum_a>Tnum_b)Tnum_compare=2;
else if(Tnum_a<Tnum_b)Tnum_compare=1;
i=Thead+Twidth*Tnum_a;
j=Twidth*Tnum_b;
for(k=0;a[i+k]==b[k] && b[k]==b[j+k];k++);
if(a[i+k]==b[j+k]){
if(a[i+k]>b[k]){break;} //a=b>t
else{ //t>a=b
if(!trend_a){break;}
if(Tnum_compare==0){
i+=k+1;
Twidth*=Tnum_a;
Twidth+=k+1;
Tnum_a=Tnum_b=1;
goto cycle;
}
if(Tnum_compare==1){continue;}
}
}else if(a[i+k]>b[j+k]){
if(b[k]>a[i+k]){ //t>a>b
if(!trend_b || Tnum_compare==1)continue;
}else if(b[k]==a[i+k]){ //t=a>b
if(trend_a==2){
if(!trend_b)break;
}else if(trend_b==0 && trend_a==0) break;
else if(!trend_b || trend_a && Tnum_compare==1)
continue;
}else if(b[k]>b[j+k]){ //a>t>b
if(!trend_b)break;
}else if(b[k]==b[j+k]){ //a>t=b
if(trend_b!=1)break;
}else break; //a>b>t
}else{
if(b[k]>b[j+k]){ //t>b>a
if(Tnum_compare!=2 && trend_a){continue;}
}else if(b[k]==b[j+k]){ //t=b>a
if(trend_b!=1 || Tnum_compare!=2 && trend_a){continue;}
}else if(b[k]>a[i+k]) continue; //b>t>a
else if(b[k]==a[i+k]){ //b>t=a
if(trend_a==2){break;}
continue;
}else break; //b>a>t
}
i=Thead;break;
}
for(j=0;j<i;j++) c[j]=a[j];
for(j=0;b[j];j++) c[i+j]=b[j];
for(j+=i;a[i];i++) c[j++]=a[i];
c[j]='\0';
return;
}[/code]
23 楼
fenix124 [专家分：70] 发布于 2009-07-06 17:13:00
刚才看了下题目，发觉似乎可以用KMP匹配的思想来做，待插入的串每次作最少回退。
我来回复
您所在位置：