首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串
  • 热度指数：163273 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。
所谓回文串，指左右对称的字符串。
所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串
数据范围：字符串长度
进阶：时间复杂度：，空间复杂度：

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


输出描述:
返回最长回文子串的长度
示例1

输入

cdabbacc

输出

4

说明

abba为最长的回文子串
算法知识视频讲解
添加回答
C
今天干饭了没头像 今天干饭了没 
#include <stdio.h>
#include <string.h>

char s[350];
int check_str(int a,int b)
{
    while(a<b)
    {
        if(s[a]!=s[b])
            return 0;
        a++;
        b--;
    }
    return 1;
}

int main() {
    int a, b;
    int max = 0;
    gets(s);
    
    for(a=0;a<strlen(s);a++)
    {
        for(b=strlen(s)-1;b>a;b--)
        {
            if(s[a]==s[b])
            {
                if(check_str(a,b))
                {
                    int len = b-a+1;
                    if(max < len)
                        max = len;
                    continue;
                }
            }
        }
    }
    printf("%d",max);
    return 0;
}

发表于 2024-04-16 21:20:10 回复(0)
C
zsfyydgj头像 zsfyydgj 
#include <stdio.h>
int iszichuan(char *str)
{
    int n=strlen(str);
    for(int i=0;i<n/2;i++)
    {
        if(str[i]!=str[n-i-1])
        return 0;
    }
    return n;
}
int main() {
    char str[351];
    int len=0;
    scanf("%s", str);
    for(int i=0;i<strlen(str);i++)
    {
        char str1[351]={'\0'};
        for(int j=i;j<strlen(str);j++)
        {
            str1[j-i]=str[j];
            if(len<iszichuan(str1))
            len=iszichuan(str1);
        } 
    }
    printf("%d",len);
    return 0;
}

发表于 2023-11-06 22:35:03 回复(0)
C
彭洋a头像 彭洋a
#include <stdio.h>
#include <string.h>

int isstr(char* left,char* right)
{
    while(left<=right)
    {
        if(*left - *right == 0)
        {
            left++;
            right--;
        }
        else {
        return 0;
        }
    }
    return 1;
}

int main() {
    char str[351] = {'\0'};
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        int ret = 0;
        for(int i = 0;i<len-1;i++)
        {
            for(int j = i+1;j<len;j++)
            {
                if(isstr(&str[i],&str[j]))
                {
                    ret = ret>j-i+1?ret:j-i+1;
                }
            }
        }
        printf("%d\n",ret);
    }
    return 0;
}
发表于 2023-10-13 22:32:40 回复(0)
C
积极的懒羊羊只想搞钱头像 积极的懒羊羊只想搞钱 
#include <stdio.h>
#include<string.h>
int main() 
{
    int a,n,b,i,j,k,l=0;
    char c[350];
    scanf("%s",c);
    a=strlen(c);
    for(i=1;i<a;i++)
    {
        for(n=0,j=i-1,k=i;j>=0&&k<a;j--,k++)
        {
            if(c[j]==c[k])n=n+2;
            else break;
        }
        if(l<n)l=n;
            for(n=1,j=i-1,k=i+1;j>=0&&k<a;j--,k++)
        {
            if(c[j]==c[k])n=n+2;
            else break;
        }
        if(l<n)l=n;
    }
    printf("%d",l);
    return 0;
}

发表于 2023-08-29 18:17:34 回复(0)
C
梦游异世间头像 梦游异世间 
// 中心扩展查找，分两种情况：aba   abba
// 这两种情况没尝试是否可以合并
#include <stdio.h>
#include <string.h>
 
int main() {
    int len = 0, b = 0;
    int max = 0;
    char str[350];
 
    memset(str, 0, sizeof(str));
 
    while (scanf("%s", str) != EOF) {
        len = strlen(str);
 
        // 第一种情况：abba
        for(int i = 0; i < (len - 1); i++) {
            if(str[i] == str[i + 1]) {
                for(int j = 0; (j <= i) && (j <= len - 1 - i); j++) {
                    if(str[i - j] == str[i + 1 + j]) {
                        if(max < ((j + 1) * 2))
                            max = (j + 1) * 2;
                    } else
                        break;
                }
            }
        }
 
        // 第二种情况：aba
        for(int i = 0; i < (len - 2); i++) {
            if(str[i] == str[i + 2]) {
                for(int j = 0; (j <= i) && (j <= len - 2 - i); j++) {
                    if(str[i - j] == str[i + 2 + j]) {
                        if(max < (((j + 1) * 2) + 1))
                            max = ((j + 1) * 2) + 1;
                    } else
                        break;
                }
            }
        }
        printf("%d\n", max);
    }
    return 0;
}

发表于 2023-08-20 22:48:37 回复(0)
C
Jackn头像 Jackn 
#include <stdio.h>

int main() {
    char s[360];
    gets(s);
    int i=0, j=0, length=0 ,maxlength1=0,maxlength2=0 ;
    for(i=0;  i+1 < strlen(s);  i++){
        if( s[i] == s[i+1] )  {
            for( length=1, j=1;  i-j>=0 && i+j+1 < strlen(s); j++ ){
                if(s[i-j]==s[i+j+1]) length++;
                else break;
            }
            if(length>maxlength1)  maxlength1=length;
        }
    }
    maxlength1*=2;  //以上是偶数回文序列的最大长度，下面计算奇数回文序列的最大长度；
    
    for(i=1,length=0;  i+1 < strlen(s);  i++){
       
            for( length=0, j=1;  i-j>=0 && i+j < strlen(s); j++ ){
                if(s[i-j]==s[i+j]) length++;
                else break;
            }
        if(length>maxlength2)  maxlength2=length;
    }
    maxlength2=maxlength2*2+1;
    if(maxlength2>maxlength1)  printf("%d",maxlength2);
    else printf("%d",maxlength1);

    return 0;
}

发表于 2023-03-28 16:51:06 回复(0)
C
好久不见，最近好吗头像 好久不见，最近好吗
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    int i = 0,j = 0,len = 0,max = 0,tmp = 0;
    char str[351] ={'\0'};
    char dp[351][351] = {{0}};
    
    while(scanf("%s",str)!=EOF)
    {
        memset(dp,0,351*351);
        len = strlen(str);
        for(i = len -1; i>=0;i--)
        {
            for(j = i;j< len;j++)
            {
                if(i == j)//长度为1的字串
                {
                    dp[i][j] = 1;

                    max = (max > (j-i+1)) ? max:(j-i+1);
                }
                else if(str[i] == str[j] && (j-i) == 1)//相邻两个一样字符组成的字串
                {
                    dp[i][j] = 1;
                    max = (max > (j-i+1)) ? max:(j-i+1);
                }
                else if(str[i] == str[j] && dp[i+1][j-1])//两个一样字符中间插着字串组成的字串
                {
                    dp[i][j] = 1;
                    max = (max > (j-i+1)) ? max:(j-i+1);
                }
            }
        }
        printf("%d\n",max);       
    }    
    return 0;   
}
发表于 2022-06-19 00:52:26 回复(0)
C
完全没头绪头像 完全没头绪 
#include<stdio.h>
#include<string.h>
int main()
{
    int i,k,count,n,len;
    n=0;
    char str[351]="\0";
    scanf("%s",str);
    len=strlen(str);
    for(i=0;i<len;i++)
    {
        k=0;
        count=0;
        while((str[i+k]==str[i-k])&&((i+k)<len)&&((i-k)>=0))//aba型
        {
            count++;
            k++;
        }
        if (n<(count*2-1))
            n=count*2-1;
        k=0;
        count=0;
        while((str[i+1+k]==str[i-k])&&((i+1+k)<len)&&((i-k)>=0))//aaa型
        {
            count++;
            k++;
        }
        if (n<count*2)
            n=count*2;
    }
    printf("%d\n",n);
    return 0;
}
用i试遍每一个字符，以那个字符为中心检测它的最长回文子串

发表于 2022-05-07 17:21:26 回复(0)
C
李拓爱编码头像 李拓爱编码 
#include<stdio.h>
#include<string.h>

#define STR_MAX    1000

char* reverse(char* str, int len);
int IfPlalindrome(char* str, int len);
int substr(char* str, int len);
    
//反转字符串
char* reverse(char* str, int len)
{
    if ((str == NULL) || (len == 0))
    {
        return NULL;
    }
    
    char* p = (char*)malloc(sizeof(char) * (len + 1));
    if (p == NULL)
    {
        return NULL;
    }
    
    memset(p, 0, (sizeof(char) * (len + 1)));
    
    int i;
    for (i = 0; i < len; i++)
    {
        p[i] = str[len - 1 -i];
    }
    p[i] = '\0';
    
    return p;
}

//判断是否是回文串
int IfPlalindrome(char* str, int len)
{
    if ((str == NULL) || (len == 0))
    {
        return 0;
    }
    
    int left = 0;
    int right = len - 1;
    
    while (left < right)
    {
        if (str[left] != str[right])
        {
            return 0;    //不是回文，返回0
        }
        left++;
        right--;
    }
    
    return 1;
}

//最长回文子串
/*
思想：
反转 S，使之变成 S’。找到 S 和 S’之间最长的公共子串，这也必然是最长的回文子串。
理由：如果找两个字符串的公共子串，i指向第一个字符串，j指向第二个字符串，用暴力求解法肯定就是i每走一步，j就不断的从头遍历第二个字符串，然后判断是否相等。
j从前往后走，就相当于原字符串从后向前走
*/
int substr(char* str, int len)
{
    if ((str == NULL) || (len == 0))
    {
        return 0;
    }
    
    char arr[STR_MAX];    //公共子串
    int max = 0;
    char* p = reverse(str, len);
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < len; j++)
        {
            int m = i, n = j, k = 0;
            while (str[m] == p[n])
            {
                arr[k] = str[m];
                m++;
                n++;
                k++;
            }
            
            arr[k] = '\0';
            
            if (IfPlalindrome(arr, strlen(arr)))
            {
                if (strlen(arr) > max)
                {
                    max = strlen(arr);
                }
            }
        }
    }
    
    free(p);      //释放堆内存，防止内存泄露
    p = NULL;     //与NULL绑定，防止野指针
    
    return max;
    
}

int main()
{
    char str[STR_MAX];
    int max, len;
    while (scanf("%s", str) != EOF)
    {
        len = strlen(str);
        max = substr(str, len);
        printf("%d\n", max);
    }

    return 0;
}

发表于 2021-10-09 11:34:20 回复(0)
C
海饼干666头像 海饼干666 
#include <stdio.h>
#include <string.h>

int main()
{
    int len = 0;
    char tmp;
    char inarray[1024];
    
    while(scanf("%c",&tmp) != EOF)
    {
        if(tmp != '\n')
        {
            inarray[len++] = tmp;
        }
        else
        {
            if(len <= 1)
            {
                printf("%d\n",len);
                continue;
            }
            
            int width = 1,begin = 0, end = 0;
            for(begin = 0; begin < len-1; begin++)
            {
                for(end = len-1; end >= 0; end--)
                {
                    int state = 0,left = begin, right = end;
                    while(begin <= right)
                    {
                        if(inarray[left] == inarray[right]) 
                        {
                            left++;
                            right--;
                        }
                        else 
                        {
                            state = 1;
                            break;
                        }
                    }
                    if(!state)
                    {
                        width = width<(end-begin+1)?(end-begin+1):width;
                    }
                }
            }
            len = 0;
            printf("%d\n",width);
        }
    }
    return 0;
    
}

发表于 2021-09-05 15:18:01 回复(0)
C
牛客109610529号头像 牛客109610529号

#include<stdio.h>

#include <string.h>

int main() {

    char str[1024];

    fgets(str,1024,stdin);

    int m = strlen(str);

    int n = m;

    int maxLen = 0;

    int dp[m][n];

    for (int i = 0; i < m; i++)

        for (int j = n - 1; j >= 0; j--)

            if (str[i] == str[j]) {

                if(i==0||j==n-1)

                {

                    dp[i][j]=1;

                }

                else{

                dp[i][j] = dp[i - 1][j + 1] + 1;

                }

                    maxLen=maxLen>dp[i][j]?maxLen:dp[i][j];

            }else{

                dp[i][j]=0;

            }

    printf("%d\n",maxLen);

}

发表于 2021-08-21 01:31:29 回复(0)
提交观点

问题信息

字符串 穷举
难度：
16条回答 31486浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号