原理可参考链接：https://blog.csdn.net/sinat_35261315/article/details/78267046?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&utm_relevant_index=2
# 最大回文子串
def LongestPlindromeSubseq(str):
if len(str) <= 1:
return str
ans = ''
# 以extend_s[i]为中心，向两边扩展，这个extend_s[i]既有可能是#，也有可能是字母
for i in range(2*len(str)+1):
ans = Find_Plindrome(i-1,i+1,str,ans)
return ans
def Find_Plindrome(l_idx,r_idx,str,ans):
# 判断边界，从中间往两边查找，遇到左右不相等说明回文断开，就停止
while l_idx>=0 and r_idx<2*len(str)+1:
# 的下标永远是偶数，所以判断是否是奇数，然后比较s中的两个字符
if l_idx%2!=0 and r_idx%2!=0 and str[l_idx//2]!=str[r_idx//2]:
break
l_idx -= 1
r_idx += 1
'''
* 这是为了解决边界0的问题，因为如果找到左边界(0)时仍然相等，那么l_idx会是-1
* 因为找到的回文子串应该是s[l_idx / 2 + 1, r_idx / 2]
* 由于l_idx是-1，-1/2==0，正常结果应该是s[0, r_idx / 2 - 1]，
* 会导致l_idx / 2 + 1 == 1，不为0，使结果长度变小
'''
l_idx = -2 if l_idx is -1 else l_idx
l_idx_ = l_idx//2 + 1
r_idx_ = r_idx//2
if len(ans) < r_idx_ - l_idx_:
ans = str[l_idx_:r_idx_]
return ans
str = 'abcbcb'
print(LongestPlindromeSubseq(str))
