7-64 最长对称子串
我的代码：
1 #include<stdio.h> 2 #include<string.h> 3 #define N 1001 4 5 int main() { 6 char str[N]; 7 int len; 8 gets(str); 9 len=strlen(str); 10 int i=0,j=0,sys=0,lng=1,temp=0; 11 for(i=2; i<len; i++) { 12 if(sys==0) { 13 j=i-2; 14 if(str[j]==str[i]) { 15 sys=1;temp=3;j--; 16 if(j<0) sys=0; 17 } 18 } else { 19 if(str[j]==str[i] && j>=0) { 20 temp+=2;j--; 21 } else { 22 sys=0; 23 } 24 } 25 if(temp>lng) lng=temp; 26 } 27 sys=0;temp=0; 28 for(i=1; i<len; i++) { 29 if(sys==0) { 30 j=i-1; 31 if(str[j]==str[i]) { 32 sys=1;temp=2;j--; 33 if(j<0) sys=0; 34 } 35 } else { 36 if(str[j]==str[i] && j>=0) { 37 temp+=2;j--; 38 } else { 39 sys=0; 40 } 41 } 42 if(temp>lng) lng=temp; 43 } 44 printf("%d",lng); 45 }
（一个用例通不过）
思考过程：
数组存储字符串，指针i从头遍历
str[i-2]==str[i]，若相等则记录对称串的长度，同时指针j从i-2开始向后遍历
两个指针所指内容不相等时停止遍历，更新对称串的长度
奇数情况
变量：
字符数组str
指针i、j
状态变量sys——当前对称串是否在增长
temp——当前对称串长度
lng——当前最长对称串长度
细节：
i从2开始遍历，按照sys的状态分两种情况
若sys==1,判断str[i]==str[j]，若是则temp+=2，j--；
若否或j<0则sys=0，跳出 15
若sys==0，判断str[i]==str[i-2]，若是则sys=1，j-- 16
更新lng
边界：
调试：
a 1
aba 3
abcba 5
ababa 5
a a 3
偶数情况
奇偶切换
性能优化
大神的代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> using namespace std; int main() { char str[1010]; gets(str); int maxn=0,tmp; int len = strlen(str); string str; getline(cin,str); int len = str.length(); for(int i=0;i<len;i++) { tmp = 1;//奇数时的情况，tmp不同呀！！！ for(int j=1;j<=len;j++) { if(i-j<0 || i+j>=len || str[i-j]!=str[i+j]) break;//不满足条件了，就跳过，此时的tmp就是i中最长字符串 tmp += 2; } maxn = max(maxn,tmp); tmp = 0;//偶数时的情况 for(int j=1;j<=len;j++) { if(i+1-j<0 || i+j>=len || str[i-j+1]!=str[i+j]) break; tmp += 2; } maxn = max(maxn,tmp); } cout << maxn << endl; return 0; }
差距：
1、过于侧重从流程层面思考问题，而不是从逻辑层面思考问题