回文
Manacher 算法
给你一个字符串 s，找到 s 中最长的回文子串。
参考：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
求以i为center的边长，仅对奇数长度有效。如果要涉及偶数，可以空白处添加#，变身下。
这里边长0表示a，边长1表示aaa
'''
须先变为回文皆奇数长度, 可提前转换: s1 = '#' + '#'.join(list(s)) + '#'
'''
n = len(s)
arm_len = [0] * n
def expand(left, right):
while 0 <= left and right < n and s[left] == s[right]:
left, right = left - 1, right + 1
r = right - left + 1
return r // 2 - 1
right = -1
id = -1
for i in range(n):
if right > i:
arm_len[i] = min(right - i, arm_len[2 * id - i])
arm_len[i] = expand(i - arm_len[i], i + arm_len[i])
else:
arm_len[i] = expand(i, i)
if i + arm_len[i] > right:
id = i
right = i + arm_len[i]
时间复杂度o(n).
根据以上得到的arm_len 判断某个子串是不是回文。
def is_palindrome(s, i, j, armlen):
mid = (i + j) // 2 # 前半部分或中间
# 找中心点，然后对应到s1上
t = 2 * mid + 1
if (j - i + 1) % 2 == 0:
t += 1
return armlen[t] >= j - i + 1
回文技巧
DP:
- 用 P(i,j) 表示字符串 s 的第 i到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串 . 变成区间dp
应用
- 647. 回文子串 给你一个字符串
s，请你统计并返回这个字符串中 回文子串 的数目。1.中心扩展o(n2), 2. manacher o(n) - 6236. 不重叠回文子字符串的最大数目 实际是dp，判断s(i,j)是不是回文。