73.对策字符串的最大长度。
题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串
“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出 4。
分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的
加强版。
/* 73.对策字符串的最大长度。 题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串 “google”,由于该字符串里最长的对称子字符串是“goog”,因此输出 4。 分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的 加强版。 1.最简单的就是得到输入字符串的所有子字符串,并逐个判断是不是对称的。 如果一个子字符串是对称的,我们就得到它的长度。判断是否对称,就是首尾判断是否相等 2.从中间开始,找对称字符,首先找出对称中心(a[i]==a[i+1]),然后从对称中心开始向两边移动比较 从字符串的每个字符串两端开始延长,如果当前的子字符串是对称的, 再判断延长之后的字符串是不是对称的。由于总共有O(n)个字符,每个字符可能延长O(n)次, 每次延长时只需要O(1)就能判断出是不是对称的,因此整个函数的时间效率是O(n^2)。 还要注意考虑奇偶情况 */ #include<iostream> #include<stdio.h> using namespace std; int getSymLen(char *str) { int len,i,max,left,right,k1,k2;//k1 k2记录位置 len=strlen(str); max=1;//最小为1 排除空的 for(i=0;i<len-1;i++) { left=i-1;//以当前i为中心 奇的情况 左右延展 right=i+1; while(1) { if(left<0||right>len-1||str[left]!=str[right]) break; left--; right++; } if(right-left-1>max)//right-left+1-2 { max=right-left-1; k1=left+1; k2=right-1;//最后个是不成功的 } left=i;//以当前i为中心 偶的情况 左右延展 right=i+1; while(1) { if(left<0||right>len-1||str[left]!=str[right]) break; left--; right++; } if(right-left-1>max) { max=right-left-1; k1=left+1; k2=right-1; } } for(i=k1;i<=k2;i++) cout<<str[i]; return max; } int main() { char str[100]; while(scanf("%s",str)) { cout<<str<<":对策字符串的最大为:"; cout<<" 长度为:"<<getSymLen(str)<<endl; } return 0; } /* google daaccacdaaaddf abaab aba aaaaa agollloge */ /* 有问题的方法 int getSymLen(char *str) { int len,i,sum,max,left,right; len=strlen(str); max=0; for(i=0;i<len-1;i++) { if(str[i]==str[i+1]) { sum=2; left=i-1; right=i+2; while(1) { if(left<0||right>len-1||str[left]!=str[right]) break; left--; right++; sum+=2; } if(sum>max) max=sum; } } return max; }*/