列表

详情


KS5. 回文子串

描述

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
("回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。)
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

数据范围:字符串长度满足  

输入描述

输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。

输出描述

符合条件的字符串有"a","a","aa","b","c","b","bcb"

所以答案:7

示例1

输入:

aabcb

输出:

7

原站题解

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2020-07-07

#include<iostream>
#include<string>
using namespace std;
int dp[55][55];
int main() {
 string s;
  cin>>s;
 int len = s.size(), ans = 0;
 for(int i=len-1; i>=0; i--) {
     for(int j=i; j<len; j++) {
         if(i == j) dp[i][j] = 1;
         else if(j-i==1) dp[i][j] = (s[i]==s[j]);
         else dp[i][j] = (dp[i+1][j-1]==1&&s[i]==s[j]);
         ans += dp[i][j];
     }
 }
 cout<<ans<<endl;
 return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2021-09-21

#include <stdio.h>
#include <string.h>

int main()
{
    char s[55];
    while(scanf("%s",s)!=EOF)
    {
        int len=strlen(s);
        int sum=len;
        for(int i=0;i<len;i++)
        {
            int j;
            for(j=1;i-j>=0 && i+j <len;j++)
            {
                if(s[i-j]==s[i+j])
                    sum++;
                else
                    break;
            }
            for(j=0;i-j>=0 && i+j+1<len;j++)
            {
                if(s[i-j]==s[i+j+1])
                    sum++;
                else
                    break;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-12-24

#include<stdio.h>
#include<string.h>
int main(void)
{
    char a[100];
    int num=0,i,j,len;
    scanf("%s",&a);
    len=strlen(a);
    for(i=1;i<len;i++)
    {
        if(a[i-1]==a[i])
        {
            num++;
            for(j=1;j<(len+1)/2;j++)
            {
                if(a[i-j-1]==a[i+j])
                    num++;
                else
                break;
            }
        }
    }
    for(i=1;i<len;i++)
    {
        for(j=1;j<(len+1)/2;j++)
        {
            if(a[i-j]==a[i+j])
                num++;
            else
            break;
         }
    }
    num=num+len;
    printf("%d\n",num);
    return 0;
 
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-03-19

#include <stdio.h>
#include <string.h>

void mystrrev(char *des,const char *src)
{
    int i,len = strlen(src);
    src += len-1;
    for(i=0;i<len;i++){
        *des++ = *src--;
    }
    *des = '\0';
}

int main()
{
    char arr1[51],arr2[51],arr3[51];
    int i,j,len,cnt;
    while(scanf("%s",arr1)!=EOF){
        len = strlen(arr1);
        for(i=0,cnt=0;i<len;i++){
            for(j=1;j<=len-i;j++){
                memcpy(arr2,arr1+i,j);
                arr2[j] = '\0';
                mystrrev(arr3,arr2);
                if(!strcmp(arr2,arr3)) cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2019-08-01

#include<stdio.h>
int main()
{
    int num1=0,len,i,j;
    char S[100];
    scanf("%s",&S);
    len=strlen(S);
    for(i=1;i<len;i++)
    {
        if(S[i-1]==S[i])
        {
            num1++;
            for(j=1;j<(len+1)/2;j++)
            {
                if(S[i-1-j]==S[i+j])
                {
                    num1++;
                }
                else{break;}
            }
        }
    }
    
    for(i=1;i<len;i++)
    {
            for(j=1;j<(len+1)/2;j++)
            {
                if(S[i-j]==S[i+j])
                {
                    num1++;
                }
                else{break;}
            }
    }
    num1=num1+len;
    printf("%d",num1);
    return 0;
}

上一题