题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
不懂怎样才能写出时间复杂度为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);
}
汤臣倍健开奖53人在聊