列表

详情


HJ85. 最长回文子串

描述

给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。
所谓回文串,指左右对称的字符串。
所谓子串,指一个字符串删掉其部分前缀和后缀(也可以不删)的字符串
数据范围:字符串长度
进阶:时间复杂度:,空间复杂度:

输入描述

输入一个仅包含小写字母的字符串

输出描述

返回最长回文子串的长度

示例1

输入:

cdabbacc

输出:

4

说明:

abba为最长的回文子串

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 1ms, 内存消耗: 324KB, 提交时间: 2021-07-25

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){

    char a[1000];
 while(scanf("%s",a)!=EOF){
    int l=strlen(a);

    int len=1,le,ri,maxlen=1;
    for(int i=1;i<l-1;i++)
    {
        le=ri=i;
        len=1;
        while(le-1>=0&&a[i]==a[le-1]){
            len++;
            le--;
        }
        while(ri+1<=l&&a[i]==a[ri+1]){
            ri++;
            len++;
        }
         //    printf("  %d  %d\n",le,ri);
        while(le-1>=0&&ri+1<=l&&a[le-1]==a[ri+1])
        {
            len+=2;
            le--;
            ri++;
        }
        maxlen=fmax(maxlen,len);
          //   printf("%d\n",maxlen);
    }
     printf("%d\n",maxlen);
}
    
   return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 356KB, 提交时间: 2021-09-07

#include <stdio.h>
#include <string.h>
int main()
{
    char str[1000];
    while(gets(str))
    {
        
        int size=strlen(str);
       int max=0;
        int max1=0;
        int max2=0;
        for(int i=0;i<size;i++)
        {
            int j,k;
             //奇数
            for( j=i,k=i+1;j>=0,k<size;j--,k++)
            {
                if(str[j]!=str[k])
                {
                    break;
                }
                
            }
            max1=(k-j-1)>max1?(k-j-1):max1;
            for( j=i-1,k=i+1;j>=0,k<size;j--,k++)
            {
                if(str[j]!=str[k])
                {
                    break;
                }
                
            }
            max2=(k-j-1)>max2?(k-j-1):max2;
        }
        max=max1>max2?max1:max2;
        printf("%d\n",max);
    }
    
}

上一题