回文子串的最大长度

算法1

(动态规划) $O(n^2)$

一.状态表示 dp[j][i]
1.集合：表示以i为起始下标，j为终点下标的是回文子串
2.性质：bool
二.状态计算
1.边界：j-i<3:dp[i][j]=True （结合’aa’‘aba’理解）
2.转移方程：dp[i][j]=（s[i]==s[j]）and (dp[i+1][j-1])
三.结合本题
1.要返回的是最大子串
1）最大：更新max_len值
2）子串本身：python切片

时间复杂度

参考文献

python 代码

从Leetcode5.最长回文子串变形

def longestPalindrome(s):
        #特判
        if not s:
            return ''
        #初始化
        n=len(s)
        dp=[[False]*n for _ in range(n)]
        max_len=1
        idx=0

        #特判
        for i in range(n):
            dp[i][i]=True

        #难点1.让j先遍历到最右边
        for j in range(1,n):
            for i in range(j):
                if s[i]==s[j]:
                    #难点2.特判ij边界
                    if j-i<3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                #找到回文串；更新最大值
                if dp[i][j]:
                    cur_len=j-i+1
                    if max_len<cur_len:
                        max_len=cur_len
                        idx=i
        return max_len

if __name__=="__main__":
    while 1:
        s=input()
        if s == "END":
            break
        x=longestPalindrome(s)
        print(x)

算法2

(马拉车) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla