为什么如下求最长回文子串的中心扩散算法中,把第8行挪到第6行会导致结果出错呢?
题目:
给你一个字符串s,找到s中最长的回文子串。
char * longestPalindrome(char * s){
int start=0,left,right,size,maxStart,maxSize=0,length=strlen(s);
while(start<length-maxSize/2){
left=start; //左指针来到新的中心点
printf("left=%d",left);
while(s[left]==s[++start]); //当左指针与起始标记重合时,标记右移
right=start-1; //右指针同左指针一样从中心开始
while(left>=0&&right<length&&s[left]==s[right]){
size=right-left+1;
printf("right=%d,size=%d,",right,size);
if(size>maxSize){
maxStart=left;
maxSize=size;
}
left--,right++; //从中心扩散
printf("left=%d, right=%d,",left,right);
}
printf("left=%d,right=%d,s[left]=%c,s[right]=%c",left,right,s[left],s[right]);
}
s[maxStart+maxSize]='\0';
s=&s[maxStart];
return s;
}
//输出流:
left=0right=0,size=1,left=-1, right=1
left=1right=1,size=1,left=0, right=2
right=2,size=3,left=-1, right=3
left=2right=2,size=1,left=1, right=3
right=3,size=3,left=0, right=4
left=3right=3,size=1,left=2, right=4
例如s="cbbd",原算法结果为bb;
如果改为:
char * longestPalindrome(char * s){
int start=0,left,right,size,maxStart,maxSize=0,length=strlen(s);
while(start<length-maxSize/2){
left=start; //左指针来到新的中心点
printf("left=%d",left);
right=start; //右指针同左指针一样从中心开始
while(s[left]==s[++start]); //当左指针与起始标记重合时,标记右移
while(left>=0&&right<length&&s[left]==s[right]){
size=right-left+1;
printf("right=%d,size=%d,",right,size);
if(size>maxSize){
maxStart=left;
maxSize=size;
}
left--,right++; //从中心扩散
printf("left=%d, right=%d,",left,right);
}
printf("left=%d,right=%d,s[left]=%c,s[right]=%c",left,right,s[left],s[right]);
}
s[maxStart+maxSize]='\0';
s=&s[maxStart];
return s;
}
//输出流:
left=0right=0,size=1,left=-1, right=1
left=1right=1,size=1,left=0, right=2
left=3right=3,size=1,left=2, right=4
在s="cbbd"时,输出结果为c。
恳请各位赐教为什么这一行语句的位置改动会出现这种情况,多谢。
我明白你的意思了,你是觉得第一种++之后再-1有冗余,然后就把它挪到上面去对不对?单这一句的话,确实是可以这样,但是你忘记了,那个是while循环,里面执行了可能不止一次,就是说有可能++很多次了。
比起问为什么不行,你其实更应该先看懂每一行代码是干什么用的,什么目的,起什么作用
第8行while里面有++start,
而right=start-1;这里需要start的值
那么你在start修改值之前去取它的值,和start修改之后取它的值,那取到的能是同一个值吗
-=-=-
你学编程,要了解的最重要的概念就是顺序执行。
你得对执行顺序敏感
就像子弹时间一样:
对方开枪了,你伸手接住了子弹,再拿到眼前看;
对方没开枪你就伸手去接,对方趁你看手的时候开枪了,那结局能一样吗