-
基本标记变量.
c # 对称中心 i # 中心后的字符索引值 r # 边界值, 边界是回文两端 p[i] # 忽略'#'的对称数量, 半径长 i_mirror # i点的对称点 -
基本方法是遍历字符串, 以一个字符为中心, 判断边界上的字符是否相同, 如果相同则边界值加1继续判断.
-
其将初始字符串字符间填充'#'. 巧妙地将解决对称数量奇偶的问题.
对称的关键点在于原来的字符,如果边界字符不对称,则边界值停留在'#'.如果字符对称, 则"#"始终对称, 边界值加2, 半径加1.
-
观察以下情况:
palindrome_table10.png
i 点的对称点 i' 的 p[i'] 是 1. 因为边界在 i' 的两边 '#'' 字符上, 在此时中心(c点)的边界内. 根据对称性可以得到 i 的 p[i] 最终结果等于 p[i'].
如果 i 点的对称点的边界超出了中点的边界, 如下图:
palindrome_table5.png
因为对称性, 索引值(index)21和1不对称. 所以 i 点的 p[i] 即半径长只能到中心的边界.
但有一种情况是中心点 c 左边界在字符串开头, 这时无法通过 左侧边界外情况得知右侧, 所以此时 i 点的值存在增长的可能.(其实下面还有种情况)(错误, 如果i'点的边界在c点的边界内, 则不可能增长, 如果i'点的边界超出c点的边界, 则c点左边界不可能在开头)如果 点 i' 左边界值与中心点 c 的左边界重合. 这时中心点边界外不对称, 点 i' 边界外不对称. 即中心点左边界外一点和右边界外一点不同, 点 i'同理, 存在点 c 的右边界和点 i' 的右边界相同的情况. 点 i 的左边界和点 i' 右边界值相同, 则不能得知点 c 边界外 i 的对称情况
重复说下上面的情况: 它其实就是一个等价命题转换的问题,
i左边界外一点和右边界外一点是否对称?因为c右边界和i右边界重合, 转换为i左边界外一点和c右边界外一点是否对称?因为对称, i左边界外一点和对称点i'右边界外一点相同, 转换为i'右边界外一点和c右边界外一点是否相同?因为i'左边界外一点和c左边界外一点是同一点, i'左边界外一点和右边界外一点不相同, i'左边界外一点和c右边界外一点不相同, 所以同时与一点不同的两个点存在相同的情况 -
代码
s = "bbaaaaaaccccaaaadddd"
# 在字符串中插入#
ret = "#"
for i in s:
ret = ret + i + "#"
length = len(ret)
# p是存储以每个字符为中心的回文长度的列表, 与插入#号后的字符长度相同
p = [0]*length
r = 1
c = 0
for i in range(1, length-1):
i_mirror = 2*c - i
# 第一种情况是i点现在的右边界在c点边界内
if i < r and p[i_mirror] < r - i:
p[i] = p[i_mirror]
# 第二种情况是i点现在的右边界在c点边界外
elif i < r and p[i_mirror] > r - i:
p[i] = r - i
# 第三种情况就是i点右边界和c点的右边界重合, 不能用i的对称点判断i的情况, 需要额外的操作
else:
# r-i即现在i点为中心点回文的长度
p[i] = r - i
c = i
# 确保索引不越界. i-1-p[i]是i点左边界外一点
# 为什么i-1-p[i]是边界外一点, p[i]是边界的长度, i-p[i]是左边界
# 加减法有点坑,哈哈
while ( i- 1 - p[i] >= 0 and
i + 1 + p[i] <= length - 1):
if ret[i - 1 - p[i]] == ret[i + 1 + p[i]]:
p[i] += 1
else:
break
r = i + p[i]
-
参考链接
如有错误,欢迎指正
网友评论