首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串

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

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

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

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

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

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

输入描述:

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

输出描述:

返回最长回文子串的长度

示例1

输入

cdabbacc

输出

说明

abba为最长的回文子串

算法知识视频讲解

Python

NorthXwind

# 从中心向两边扩散
def centralDiffusion(s, lp, rp):
    while lp >= 0 and rp < len(s) and s[lp] == s[rp]:
        lp -= 1
        rp += 1
    return lp + 1, rp - 1


def maximumPalindromeSubstring(s):
    n = len(s)
    res_l, res_r = 0, 0
    for i in range(n):
        lp1, rp1 = centralDiffusion(s, i, i)
        lp2, rp2 = centralDiffusion(s, i, i + 1)  # 字符串为偶数的情况
        if rp1 - lp1 > res_r - res_l:
            res_l, res_r = lp1, rp1
        if rp2 - lp2 > res_r - res_l:
            res_l, res_r = lp2, rp2
    return res_r - res_l + 1


if __name__ == '__main__':
    line = input()
    a = maximumPalindromeSubstring(line)
    print(a)

运行时间： 40 ms 占用内存：4728K

编辑于 2022-02-25 18:49:36 回复(0)

Python

牛客113724438号

'''
一开始我也不了解题意，以为字符串中心对称，有相等的数字对称就好，这个思路是错的
解题思路：
1、解题关键是连续的字符串正序和倒序排布后的字符串相同
2、递归轮询筛选出所有符合的字符串，然后用max得出字符串的长度最大的值
'''


while True:
    try:
        str0 = input()
        num = int(len(str0))
        count = 0
        for i in range(num):
            for j in range(num, i, -1):
                str1 = str0[i:j]
                if str1 == str1[::-1]:
                    count = max(count, len(str1))
                else:
                    pass
        print(count)
    except:
        break

发表于 2021-06-13 19:25:19 回复(0)

Python

kevin_cce

一个打印语句，为啥产生了两个打印结果呢？不解，本地调试也是一个结果。

发表于 2021-05-28 11:42:04 回复(0)

Python

三三不得酒吖

def aba(s,i,j):
    while i >= 0 and j < len(s) and s[i] == s[j]:
        i -= 1
        j += 1
    return s[i+1:j]


while True:
    try:
        a = input()
        res = ''
        if a:
            for i in range(len(a)):
                tmp = aba(a, i, i)
                if len(res) < len(tmp):
                    res = tmp
                tmp = aba(a,i,i+1)
                if len(res) < len(tmp):
                    res = tmp
            print(len(res))
    except:
        break

发表于 2021-05-27 23:55:11 回复(0)

Python

牛客诶谁

import sys


def func(s):
    mmax = 1
    for i in range(1, len(s)):
        if i-mmax >= 1 and s[i-mmax-1:i+1] == s[i-mmax-1:i+1][::-1]:
            mmax += 2
        elif i-mmax >= 0 and s[i-mmax:i+1] == s[i-mmax:i+1][::-1]:
            mmax += 1
    return mmax

for line in sys.stdin:
    if line.strip():
        print(func(line))

发表于 2021-05-03 14:25:40 回复(0)

Python

牛客314674748号

def cal(s):
if s == "":
return
maxlength = 1
for i in range(len(s)):
if i - maxlength >= 1 and s[i-maxlength-1:i+1] == s[i-maxlength-1:i+1][::-1]:
maxlength += 1
if i - maxlength >= 0 and s[i-maxlength:i+1] == s[i-maxlength:i+1][::-1]:
maxlength += 1
print(maxlength)
while True:
try:
cal(input())
except:
break

发表于 2021-04-21 08:42:24 回复(0)

Python

二年三班的牛客

while True:
    try:
        str = input().strip()
        if str != '':
            max_palindrome = 0
            for left in range(len(str)):
                for right in range(left + 2, len(str) + 1):
                    reversed_str = ''.join(reversed(str[left:right]))
                    if reversed_str in str and len(reversed_str) > max_palindrome / 2:
                        if str.index(reversed_str) == right:
                            max_palindrome = len(reversed_str) * 2
                        elif str.index(reversed_str) == right - 1:
                            max_palindrome = len(reversed_str) * 2 - 1
            print(max_palindrome)
    except EOFError:
        break

发表于 2021-03-28 00:29:57 回复(0)

Python

星凌九天

while True:
try:
str1=input()
str2=str1[::-1]
m=1
x=-1
for each in str1:
x+=1
for i in range(x+2,len(str1)+1):
str3=str1[x:i]
if str3 in str2:
n=len(str3)
m=n if n>m else m
if len(str1):
print(m)
except:
break

发表于 2021-03-17 15:29:39 回复(0)

Python

牛客714286811号

#该解法有问题(讨论区有很多这种这种思路) eg::abbacceddde
def get_count(str_in):
if str_in == str_in[::-1]:
return len(str_in)
count = 0
for ii in range(0, len(str_in) - 1):
if (ii - count - 1 >= 0 and str_in[ii - count - 1:ii + 1] == str_in[ii - count - 1:ii + 1][::-1]):
count += 2
if (ii - count >= 0 and str_in[ii - count:ii + 1] == str_in[ii - count:ii + 1][::-1]):
count += 1
return count

while True:
try:
str_in = input().strip()
if str_in:
print(get_count(str_in))
except Exception as e:
# print(e)
break

发表于 2021-03-02 14:05:41 回复(0)

Python

huster111

#python
while True:
    try:
        s1 = input()
        if s1:    
            s2 = s1[::-1]
            a = 0
            m = 0
            n = len(s1) 
            for i in range(n):
                if s1[i]==s2[i]:
                    a += 1
                    if a >= m:
                        m = a 
                else:
                    a = 0
            print(m)
    except:
        break

发表于 2021-01-22 21:26:31 回复(0)

Python

牛客920628480号

这道题我不会做啊，不会做

发表于 2021-01-16 22:43:12 回复(0)

Python

bancaolanmu

while True:
    try:
        input_s= input()
        if input_s:
            length = [0]
            for i in range(len(input_s)):
                for j in range(min(i,len(input_s)-i-1)):
                    if input_s[i-j] == input_s[i+j+1]:
                        length[-1] +=2
                    else:
                        break
                length.append(0)
            print(max(length))
    except:break

没有用暴力，主要的idea是先找到相邻两个一样的字母，然后向外扩散。可能是个蠢的方法，debug了好久...估计考试的时候就gg了

编辑于 2020-12-24 05:16:24 回复(0)

Python

Littleclam

def Longest(s):
res = ''

for i in range(len(s)):
len1 = getLongest(s, i, i)
if len(len1) > len(res):
res = len1

len2 = getLongest(s, i, i + 1)
if len(len2) > len(res):
res = len2

return len(res)

def getLongest(s, l, r):
while l >= 0 and r <= len(s) - 1 and s[l] == s[r]:
l = l - 1
r = r + 1
pass
return s[l + 1:r]

while True:
try:

strings = input()

#输入为空好坑啊

if strings == '':
break
else:

res = Longest(strings)
print(res)

pass
except:
break

发表于 2020-12-16 11:32:55 回复(0)

Python

大溪地渔民

动态规划：

def cal(s):
    l = len(s)
    temp = 0
    m = [
        [0] * l for _ in range(l)
    ]
    
    for j in range(l):
        for i in range(j+1):
            if i == j:
                m[i][j] = 1
            elif j == i+1 and s[i] == s[j]:
                m[i][j] = 1
            elif m[i+1][j-1] == 1 and s[i] == s[j]:
                m[i][j] = 1
            if m[i][j] == 1:
                temp = max([temp, j-i+1])
                
    return temp


for s in sys.stdin:
    s = s.strip()
    if s:
        print(cal(s))

另一种解法：

def cal(s):
    temp = 0
    for i in range(len(s)):
        if i > temp and s[i-temp-1:i+1] == s[i-temp-1:i+1][::-1]:
                temp += 2
                continue
        if s[i-temp:i+1] == s[i-temp:i+1][::-1]:
                temp += 1
    return temp 


for s in sys.stdin:
    s = s.strip()
    if s:
        print(cal(s))

发表于 2020-12-13 16:13:55 回复(0)

Python

乐观的lishan

# 2020年11月14日20:33:52
while True:
    try:
        password = input()
        length = 1
        change = 1
#       长度发生变化，且长度小于等于密码串总长度
        while change and (length <= len(password)):
            for i in range(len(password)-length+1):
#               若当前截取的子串也在密码串逆串中,属于题目要求的对称密码，长度发生变化
                if password[i:i+length] in password[::-1]:
                    length += 1
                    change = 1
                    break
#               若当前截取的子串不在密码串逆串中,长度不变，继续下一次循环
                else:
                    change = 0
#       当长度不再变化时，输出最大对称密码长度
        if change == 0:
            print(length-1)
    except:
        break

编辑于 2020-11-14 21:28:32 回复(0)

Python

牛客658577905号

DP解法

while True:
    try:
        string=input().strip()
        n=len(string)
        if string=='': #字符串为空时
            break
        dp=[[0]*n ]*n
        maxlen=1
        for l in range(n):#遍历所有可能的字符串长度
            for i in range(n):
                j=i+l
                if j>= n:
                    break
                if l==0:#字符串长度为1，i==j
                    dp[i][j]= 1
                elif l==1:#字符串长度为2，i+1==j
                     if string[i]==string[j]:
                            dp[i][j]=2
                            if dp[i][j]>maxlen:
                                maxlen=dp[i][j]#记录最大长度回文
                else:#其他情况
                    if dp[i+1][j-1]==(j-i-1)and (string[i]==string[j]):
                        dp[i][j]=dp[i+1][j-1]+2
                        if dp[i][j]>maxlen:
                            maxlen=dp[i][j]#记录最大长度回文
        print(maxlen)
    except:
        break

发表于 2020-10-19 13:59:49 回复(0)

Python

牛客490386548号

第75题公共字符串计算的解法（滑动切片）可以参考适用，比较简洁。虽然还没想通其中的原理，先用起来。

while True:
    try:
        content = input()
        if content:
            rvsContent = content[::-1]
            n = 0
            for i in range(len(content)):
                if content[i-n:i+1] in rvsContent:
                    n += 1
            print(n)
    except EOFError:
        break

发表于 2020-10-02 21:48:31 回复(1)

Python

牛客902100313号

while True:
try:
str = input()
list = list(str)
len1 = len(list)-1
count = 0
for index in range(0,len1):
if (list[index] == list[index+1]):
i = 1
count = max(i,count)
if ((index-i) >= 0) & ((index+1+i) <= len1):
while list[index-i] == list[index+1+i]:
i += 1
count = max(i,count)
if ((index-i) < 0)|((index+1+i) > len1):
break
count = 2*count
print(count)
except:
break

发表于 2020-09-08 22:48:24 回复(0)

Python

功诚狮

def ishuiwen(s):
    mid = int(len(s)/2)
    s1 = s[mid:] if len(s)%2==0 else s[mid+1:]
    if s[:mid]==s1[::-1]:
        return True
    return False
s = input()
m = 1   
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if ishuiwen(s[i:j]):
#             print(j)
            m = max(len(s[i:j]),m)
#             print(len(s[i:j]),m)
print(m)

发表于 2020-09-06 00:39:45 回复(0)