首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串
  • 热度指数：184486 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由小写字母构成的字符串 s，求出其最长回文子串的长度。

\hspace{15pt}子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
\hspace{15pt}一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm len}(s) \leqq 350、仅由小写字母构成的字符串 s。


输出描述:
\hspace{15pt}输出一个整数，表示字符串 s 的最长回文子串的长度。
示例1

输入

cdabbacc

输出

4

说明

\hspace{15pt}在这个样例中，\texttt{ 是最长的回文子串。
示例2

输入

a

输出

1
算法知识视频讲解
添加回答
C
牛客147063978号头像 牛客147063978号 
#include <stdio.h>
#include <string.h>
int ishui(char* str, int a, int b) {
    for (int i = a, j = b; i <= (a + b) / 2 && j >= (a + b) / 2; i++, j--) {
        if (str[i] != str[j]) {
            return 0;
        }
    }
    return 1;
}
int main() {
    char str[350];
    scanf("%s", str);
    int len = strlen(str);
    int max = 1;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if ( str[i] == str[j] && ishui(str, i, j) ) {
                if ( max < j - i + 1) {
                    max = j - i + 1;
                }
            }
        }
    }
    printf("%d", max);
    return 0;
}

发表于 2025-07-26 10:16:24 回复(0)
C
牛油果114514头像 牛油果114514
思路就是使用两个指针，从字符串两头寻找一样的值，然后进入子函数。
子函数需要做的是：从传入相等值的两个指针开始向中间遍历，如果还一样就继续计数，
直到出现不一样的将计数清零，或者到两指针距离差1或相等，说明已经完成了此次记录，将记录的数传出去。 
#include <stdio.h>
#include <string.h>

#define maxstrlen 350
int string(char *s1, char *s2);

int main()
{
    char str[maxstrlen];
    int len;
    int n, m = 0;
    int i, j;

    memset(str, 0, sizeof(str));
    scanf("%s", str);
    len = strlen(str);
    if (len == 1) // 这个方法无法应对字符串只有一个字符的情况，需要特殊应对
    {
        printf("1");
        return 0;
    }
    for (i = 0; i < len; i++)
    {
        for (j = len; j > i; j--)
        {
            if (str[i] == str[j])
            {
                n = string(&str[i], &str[j]);
                m = m < n ? n : m;
                if (m == len) // 说明字符串只由一种字符构成，特殊情况
                {
                    break;
                }
            }
        }
    }
    printf("%d", m);
    return 0;
}

int string(char *s1, char *s2)
{
    int n = 2; // 假设其是，这就是进来的门槛

    while (s1 != s2 && s1 + 1 != s2) // 双指针中间有奇或偶，不能让他们走岔开
    {
        s1++;
        s2--;
        if (*s1 == *s2)
        {
            if (s1 == s2) // 应对ABA情况的正确计数
            {
                n++;
                return n;
            }
            else
            {
                n += 2;
            }
        }
        else
        {
            n = 0;
            return n;
        }
    }
    return n;
}


发表于 2025-01-24 15:50:28 回复(0)
C
雨木木的草履虫头像 雨木木的草履虫 
#include <stdio.h>
#include <string.h>
int main() {
    char arr[350];
    gets(arr);
    int len = strlen(arr);
    int count = 0;
    int max = 0, j = 0;
    for (int i = 1; i < len - 1; i++) {
        if (arr[i] == arr[i - 1]) {
            j = 0;
            count = 0;
            while ((arr[i + j] == arr[i - 1 - j]) && (i + j < len) && (i - 1 - j >= 0)) {
                count += 2;
                j++;
            }
        } else {
            j = 1;
            count = 1;
            while ((arr[i + j] == arr[i - j]) && (i + j < len) && (i - j >= 0)) {
                count+=2;
                j++;
            }
        }
        if (count > max) {
            max = count;
        }
    }
    printf("%d", max);
    return 0;
}

发表于 2024-08-19 15:57:20 回复(0)
C
执笔书生头像 执笔书生
为什么调试的结果和自测运行的结果不一致呢？
发表于 2024-07-02 20:40:23 回复(0)
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)
提交观点

问题信息

字符串 穷举
难度：
22条回答 36744浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长回文子串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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