PAT甲级：1040 Longest Symmetric String

题目描述：

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

题目大意： 

给定一个字符串 求最长回文子串的长度

解题思路： 

最长回文子串

dp[i][j] 表示 s[i] 至 s[j]如果是回文子串则为1, 反之则为0
1. s[i]==s[j]  那么只需要 s[i+1], s[j-1]是回文子串, s[i]至s[j] 就是回文子串: dp[i][j] = dp[i+1][j-1]

2. s[i]!=s[j]:
dp[i][j] = 0    s[i]至s[j]不是回文子串
根据从边界出发的原理, 注意到边界都是长度为1或2的子串, 每次转移都对子串的长度-1,  dp[i][j] = dp[i+1][j-1]

不妨考虑按子串的长度和子串的初始位置进行枚举

Python3代码： 

 
s = input()
length = len(s)
dp = [[0]*(length+10) for i in range(length+10)]
res = ''
for l in range(1,length+1) :
    i = 0 
    while i + l - 1 < length :
        j = i + l - 1
        if l == 1 : dp[i][j] = 1
        elif l == 2 and s[i] == s[j] : dp[i][j] = 2
        else :
            if s[i] == s[j] and dp[i+1][j-1] : dp[i][j] = dp[i+1][j-1] + 2
        if dp[i][j] > len(res) : res = s[i:j+1]
        i += 1
        
print(len(res))