不懂怎样才能写出时间复杂度为O(n),我只能写O(n^2)
#include <stdio.h>
#include <string.h>
int main(){
char s[350]={0};
scanf("%s",s);
int slen=strlen(s),max=1,j,k,len=0;
for(int i=0;i<slen;i++){
if(s[i]!=s[i+1] || s[i-1]==s[i+1]){//奇对称
j=i-1,k=i+1;
while(j>-1 && k<slen){//以该数为中心向两端查找
if(s[j]==s[k]){
len=k-j+1;
j--;
k++;
if(len>max){
max=len;
}
}
else{
len=0;
break;
}
}
}
if(s[i]==s[i+1]){//偶对称
j=i-1,k=i+2;
if(max<2){
max=2;
}
while(j>-1 && k<slen){//以该数为中心向两端查找
if(s[j]==s[k]){
len=k-j+1;
j--;
k++;
if(len>max){
max=len;
}
}
else{
len=0;
break;
}
}
}
}
printf("%d",max);
}

京公网安备 11010502036488号