开发者社区> 光仔december> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

九度题目1528:最长回文子串

简介:
+关注继续查看

题目1528:最长回文子串
时间限制:1 秒
内存限制:128 兆
特殊判题:否
提交:781
解决:239
题目描述:
回文串就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
回文子串,顾名思义,即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c...x,y,z组成的字符串,请输出其中最长的回文子串的长度。


输入:
输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串,字符串的长度不大于200000。


输出:
对于每组测试用例,输出一个整数,表示该组测试用例的字符串中所包含的的最长回文子串的长度。


样例输入:
abab
bbbb
abba

样例输出:
3
4
4

来源:
腾讯2013年实习生招聘二面面试题

 

有多种方法去求最长回文字串:

1.方法一:
中心求解法,从中间向两边检测,不断更新最长回文字符串大小,注意,可以分中心有一个字符的回文(奇数回文),如cabac,也有偶数的回文,如aabbaa,这要求我们要从中心或中心对称的两边字符往两边检测
AC代码:

#include<stdio.h>
#include<string.h>
char a[200010];
int FromeCenter(int l,int r,int n)//检测l至r之间的字符串中最长的回文字符串
{
     while(l>=0&&r<=n-1&&a[l]==a[r])
     {
        l--;r++;
     }
     return ((r-1)-(l+1)+1);
}
int main()
{
    int i,j,n,m,max,p1,p2;
    while(scanf("%s",a)!=EOF)
    {
       n=strlen(a);
       max=0;
       for(i=0;i<n;i++)
       {
          p1=FromeCenter(i,i,n);//以位置i为中心的最长回文字符串
          if(p1>max)
          max=p1;
          
          p2=FromeCenter(i,i+1,n);//以i和i+1之间的位置为中心的最长回文字符串
          if(p2>max)
          max=p2; 
       }
       printf("%d\n",max); 
       memset(a,0,sizeof(a));
    }
    return 0;
}


 

2.方法二,暴力求解法,只要从每个字符串开始向后检测,直至字符串的最后一个元素,检测每一个区间是否是回文字符串,更新最长的回文字符串长度;

代码(很不幸,因为长度为200000,所以华丽丽的超时了):

#include<stdio.h>
#include<string.h>
char a[200010];
int isPalinddrome(int l,int r,int n)
{
     while(l<r)
     {
        if(a[l]!=a[r])
        return 0;
        ++l;r--;
     }
     return 1;
}
int main()
{
    int i,j,n,m,max,p;
    while(scanf("%s",a)!=EOF)
    {
       n=strlen(a);
       max=0;
       for(i=0;i<n;i++)
       {
          for(j=i;j<n;j++)
          {
             if(isPalinddrome(i,j,n))
             {
                p=j-i+1;
                if(p>max)
                max=p;
             }
          }
       }
       printf("%d\n",max); 
       memset(a,0,sizeof(a));
    }
    return 0;
}



3.方法三,动态规划法
如果aba是回文,那么cabac也是回文,于是我们得到一个递推的公式:
假设s[i,j]是回文字符串的话,定义p[i,j]=1;
于是p[i,j]=1是由(p[i+1,j-1]&&s[i]==s[j])递推出来的,如此往后,直到p[i,i+1]=1,此时满足s[i]=s[i+1],最后p[i,i]=1;

这个暂时,没有写出来.....

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
最长回文子串
最长回文子串
0 0
代码随想录刷题|LeetCode 647. 回文子串 516.最长回文子序列
代码随想录刷题|LeetCode 647. 回文子串 516.最长回文子序列
0 0
代码随想录刷题|LeetCode 491.递增子序列 46.全排列 47.全排列II
代码随想录刷题|LeetCode 491.递增子序列 46.全排列 47.全排列II
0 0
回文子串(LeetCode-647)
回文子串(LeetCode-647)
0 0
LeetCode 05最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
0 0
【每日算法打卡】最长回文子串
【每日打卡系列】LeetCode 简单题 200 道
0 0
【小Y学算法】⚡️每日LeetCode打卡⚡️——5.最长回文子串
📢前言 🌲原题样例 回文串含义 🌻C#方法一:暴力法 🌻C#方法二:中心扩展法 🌻Java方法一:动态规划 🌻Java方法一:中心扩展算法 💬总结
0 0
+关注
光仔december
目前致力于JavaEE(struts/hibernate/spring/MyBatis等框架)、数据库(Mysql/oracle)、静态页面(Html/Css)技术和脚本(JavaSript/JQuery/Ajax)等技术方面的研究
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载