列表

详情


NC14517. 回文串

描述


 既然大家都知道回文串是怎么回事了,那我们就长话短说,现在有一个字符串,长度小于1200,我想知道最长的回文子串长度是多少。 

输入描述

多组输入,输入字符串只包含小写字母。

输出描述

每组输出一个数字,表示最长的回文子串。

示例1

输入:

aqppqole
ebcml

输出:

4
1

原站题解

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

Python3 解法, 执行用时: 59ms, 内存消耗: 4520K, 提交时间: 2023-02-24 23:52:00

def bijiao(x):
    if x == x[::-1]:
        return len(x)
    j = 0
    for i in range(len(x)):
        if i - j >= 0 and x[i-j:i+1] == x[i-j:i+1][::-1]:
            j += 1
        if i - j >= 1 and x[i - j -1:i+1] == x[i-j-1:i+1][::-1]:
            j += 2
            continue
        
    return j
while True:
    try:
        x = input()
        print(bijiao(x))
    except Exception:
        break

C(gcc 7.5.0) 解法, 执行用时: 10ms, 内存消耗: 280K, 提交时间: 2022-12-09 18:16:38

#include<stdio.h>
#include<string.h>
int main(){
	char a[1300];
	while(gets(a)){
	int h=strlen(a);
	int i,j;
	int max=0;
	for(i=0;i<h;i++){
		for(j=i+1;j<h;j++){
			int p=0;
			int k;
			for(k=i;k<=j;k++){
				if(a[k]!=a[i+j-k]){
					p=1;
					break;
				}
			}
			if(p==0){
				if(max<(j-i+1)){
					max=j-i+1;
				}
			}
		}
	}
	if(max==0){
		printf("1\n");
	}else{
	printf("%d\n",max);
}
}
}

C 解法, 执行用时: 2ms, 内存消耗: 360K, 提交时间: 2023-03-02 17:09:29

#include <stdio.h>
int max(int m,int n)
{
	if(m>n)
	return m;
	else 
	return n;
}
int main()
{
	char s[100000];
	while(scanf("%s",s)!=EOF)
	{
		int maxx=0,len=strlen(s);
		int i;
		for(i=0;i<len;i++)
		{
			int a=1,b=0;
			while(i-a>=0&&i+a<len&&s[i-a]==s[i+a]) a++;
			while(i-b>=0&&i+1+b<len&&s[i-b]==s[i+1+b]) b++;
			maxx=max(maxx,max(2*a-1,2*b));
		}
			printf("%d\n",maxx);
	}

 } 

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 316K, 提交时间: 2023-02-09 23:19:12

#include <bits/stdc++.h>
using namespace std;
int res;
void oper(int i,int j,string s){
	while(i>=0&&j<s.size()){
		if(s[i]!=s[j])break;
		i--;
		j++; 
	}
	res=max(res,j-i-1);
}
int main()
{
	string s;
	while(cin>>s){
		res=0;
		for(int i=0;i<s.size();i++){
			oper(i,i,s);
			oper(i,i+1,s);
		}
		cout<<res<<endl;
	}
	return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 388K, 提交时间: 2022-01-18 21:47:48

#include<iostream>
#include<algorithm>
using namespace std;
int c(int i,int j,string s){
    while(i>=0&&j<s.length()&&s[i]==s[j])i--,j++;
    return j-i-1;
}
int main(){
    string s;
    while(cin>>s){
        int res=0;
        for(int i=0;i<s.length();i++)res=max({c(i,i,s),c(i,i+1,s),res});
        cout<<res<<"\n";
    }
}

上一题