首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串

热度指数：163273 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。

所谓回文串，指左右对称的字符串。

所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串

数据范围：字符串长度 $1\le s\le 350\$

进阶：时间复杂度： $O(n)\$ ，空间复杂度： $O(n)\$

输入描述:

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

输出描述:

返回最长回文子串的长度

示例1

输入

cdabbacc

输出

说明

abba为最长的回文子串

算法知识视频讲解

Python 3

牛客30160521号

a = input()

if len(a) == 1:

print(1)

if len(a) == 2:

if a[0] == a[1]:

print(2)

else:

print(1)

if len(a) > 2:

MaxLen = 1

# 考虑奇数子串

i = 1

while i < len(a)-1:

count = 1

for j in range(min(i,len(a)-i-1)):

if a[i-j-1] == a[i+j+1]:

count += 2

MaxLen = max(MaxLen,count)

else:

break

i += 1

# 考虑偶数子串

counto = 1

if len(a) == 3:

if a[0] == a[1] or a[1] == a[2]:

counto = 2

else:

counto = 1

else:

m = 1

while m < len(a)-2:

counto = 1

if a[m] == a [m+1]:

counto = 2

MaxLen = max(MaxLen,counto)

for j in range(min(m,len(a)-m-1)):

if a[m-j-1] == a[m+1+j+1]:

counto += 2

MaxLen = max(MaxLen,counto)

else:

break

m += 1

print(MaxLen)

没什么好思路，就用很笨的方法做了

编辑于 2024-04-12 17:39:02 回复(0)

Python 3

一只酷酷的小白牛

#方法一是先对原串翻转，然后截取，即求逆串与原串的公共子串，那么回文子串是包含与公共子串的，但两者不相等，所以用例不能全部通过。方法二就先截取在翻转。

s = input()

s_r = s[::-1]

com = ''

c = 0

方法二：

for i in range(len(s),0,-1):

for j in range(0,len(s)//2+1):

if s[j:j+i] == s[j:j+i][::-1]:

com = s[j:j+i]

c = i

break

if c != 0 :

break

print(c)

# 方法一：求反转后的公共子串，有点儿bug，不知道怎么优化了

# if s == s_r:

# com = s

# c = len(s)

# else:

# for i in range(len(s)):

# if s[i-c:i+1] in s_r :

# com = s[i-c:i+1]

# c += 1

# print(c)

发表于 2023-09-29 15:43:28 回复(0)

Python 3

AlfredP

text=input().strip()
l=len(text)
f=[[0 for i in text] for j in text]
for k in range(l-1,2*l-2+1):
    for j in range(l):
        i=j+l-1-k
        if i<0:
            continue
        if i==j:
            f[i][j]=1
        elif abs(i-j)==1:
            f[i][j]=2 if text[i]==text[j] else 0
        else:
            f[i][j]=f[i+1][j-1]+2 if f[i+1][j-1]>0 and text[i]==text[j] else 0
print(max([max(i) for i in f]))

发表于 2023-05-04 17:02:30 回复(0)

Python 3

牛客428544446号

# s=input()
# dict={}
# for i in s:
# if i in dict:
# dict[i]+=1
# else:
# dict[i]=1
# max=0
# for key in dict.keys():
# if dict[key]%2==0:
# max+=dict[key]
# print(max)
orginal_str = input()
max_length = 0
for i in range(len(orginal_str)):
for j in range(1, len(orginal_str)):
if orginal_str[i:j+1] == orginal_str[i:j+1][::-1]:
if len(orginal_str[i:j+1]) > max_length:
max_length = len(orginal_str[i:j+1])
print(max_length)

发表于 2022-08-27 22:10:46 回复(0)

Python 3

刻晴宝宝啊

def pway(s1):
mstr = 0
left = 0
right = len(s1)-1
while left<=right:
if s1[left]==s1[right]:
if left==right:
mstr +=1
else:
mstr +=2
else:
mstr = 0
left+=1
right-=1
return mstr

s1 = input()
tmp = pway(s1)
for i in range(0,len(s1)-tmp-1):
for j in range(i+tmp+1,len(s1)):
curr = pway(s1[i:j])
if tmp<curr:
tmp = curr
print(tmp)

发表于 2022-08-18 13:03:03 回复(0)

Python 3

Justinshadow

s = input()
lenth = 0
for i in range(2,len(s)+1):    #根据定义回文子串最小长度2，最大长度取字符串本身
    for j in range(len(s)-i+1):    #初始下标最大取值：len(s)-i+1
        res = s[j:j+i]    #以i为窗口长度滑移
        if res == res[::-1]:
            lenth = i
print(lenth)

发表于 2022-08-09 16:09:49 回复(0)

Python 3

sir鸿

'''编写的相对复杂，主要考虑字符串如果回文，那么有两点可以肯定。

字符串长度偶数，则一定有相邻两个字符相等；奇数，则隔一位肯定有一个相等。通过这样遍历前后字符的方式找到长度，不考虑将字符装起来再输出'''

s = input()
n = 0 s_len = 0 for i in range(len(s) - 1): if len(s) % 2 == 0 : if s[i] == s[i + 1]:
            j = 1  n += 2  while i - j >= 0 and i + j < len(s) - 1: if s[i - j] == s[i + 1 + j]:
                    n += 2  j += 1  else: break  elif i+2 <= len(s)-1: if s[i] == s[i + 2]:
                j = 1  n += 3  while i - j >= 0 and i + j < len(s) - 2: if s[i - j] == s[i + 2 + j]:
                        n += 2  j += 1  else: break  if s_len < n:
        s_len = n
    n = 0 print(s_len)

发表于 2022-08-06 09:46:00 回复(0)

Python 3

649924619

while True:
    try:
        s = input()
        result = 0
        for i in range(len(s)):
            max_len = result + 1
            while i+max_len <= len(s):
                if s[i:i+max_len] == s[i:i+max_len][::-1]:
                    result = max_len
                max_len = max_len + 1
        if result !=0:
            print(result)
    except:
        break

发表于 2022-07-23 11:21:56 回复(0)

Python 3

牛客315244040号

这条用例的答案没有问题吗？abcbaaa的最长回文子串长度怎么会有5，真是无语，正式考试要是挂掉也不给看用例，就自己被坑吃哑巴亏？

发表于 2022-07-22 17:50:14 回复(0)

Python 3

牛客345614270号

str1=input()

#生成所有子串

son=[str1[j:j+i] for i in range(1,len(str1)+1) for j in range(0,len(str1)+1-i)]

#print(son)

#找出符合回文子串的长度，不符合要求的为0

son1=[len(a) if a==a[::-1] else 0 for a in son]
print(max(son1))

发表于 2022-07-14 17:02:12 回复(0)

Python 3

大橙子冲冲冲

while True:
    try:
        s = list(input())
        l = len(s)
        result = 0
        flag = 0
        for i in range(l): 
            for n in range(l - i, 2, -1):
                if s[i: i + n] == s[i: i + n][::-1]:
                    result = n
                    flag = 1
                    break
            if flag == 1:
                break
        print(result)
    except:
        break

求助！有没有大佬帮忙看看哪里有问题鸭万分感谢呜呜呜

发表于 2022-07-05 21:24:06 回复(0)

Python 3

牛客722735711号

#时间压迫下能很快想到的思维不用转弯的但很笨的方法
s=str(input())
l=[]
for i in range(len(s)):
    for j in range(len(s)):
        l.append(s[i:j+1])
x=[m for m in l if m is not '']
l2=[]
for n in x:
    if n==n[::-1] and len(n)>1:
        l2.append(n)
l3=[]
for t in l2:
    l3.append(len(t))
print(max(l3))

发表于 2022-06-17 14:45:30 回复(0)

Python 3

鱼説

while True:
try:
a = input()
b=a[::-1]
lst=[]
for i in range(len(a)):
for j in range(i+1,len(a)+1):
if a[i:j] not in b:
break
if a[i:j] == a[i:j][::-1]:
lst.append(j-i)
if lst !=[]:
print(max(lst))
except:
break

发表于 2022-05-26 22:38:05 回复(0)

Python 3

牛客950223365号

try:
n1 = input()
a = 0
str2 = ''
while True:
str1 = ''
for i in n1:
str1 = str1 + i
result = str1[::-1] # 将str1反转赋值
# print(str1, result, str2)
# print(result == str1, len(result) > len(str2))
if result in n1 and result == str1: # 如果str1 == result
if len(result) > len(str2): # 是否有比之前的回文子串长
str2 = str1
n1 = n1[1:]
if len(n1) <= len(str2): # 没有比str2更长的了
break
# print(str2)
print(len(str2))
except Exception as e:
raise e

发表于 2022-05-22 11:18:04 回复(0)

Python 3

HeartBeating

while True: 
    try:
        s = input()
        res = [] #所有回文串的长度 组成的列表
        for i in range(len(s)): # s的前指针i
            for j in range(i, len(s)): #s的后指针j，以i为起点
                if s[i:j+1] == s[i:j+1][::-1]: # 是回文串, 
                    #注意这里是 a[i:j+1]
                    #因为a[i:j]不包含a[j]
                    res.append(len(s[i:j+1])) #将长度加入到 列表
        if res != '': #[1, 1, 1, 4, 1, 2, 1, 1, 1, 2, 1]
            print(max(res))  #4 
        #print(res)
    except:
        break
###  #题目逻辑类似 65 75 85 ，两个指针，两次遍历，前后指针

发表于 2022-05-05 01:36:34 回复(0)