理解最长回文子串-马拉车算法

1. 基本标记变量.

   c # 对称中心
   i # 中心后的字符索引值
   r # 边界值, 边界是回文两端
   p[i] # 忽略'#'的对称数量, 半径长
   i_mirror # i点的对称点
   

2. 基本方法是遍历字符串, 以一个字符为中心, 判断边界上的字符是否相同, 如果相同则边界值加1继续判断.

3. 其将初始字符串字符间填充'#'. 巧妙地将解决对称数量奇偶的问题.

   对称的关键点在于原来的字符,如果边界字符不对称,则边界值停留在'#'.如果字符对称, 则"#"始终对称, 边界值加2, 半径加1.

4. 观察以下情况:
   

   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右边界外一点不相同, 所以同时与一点不同的两个点存在相同的情况

5. 代码

      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]

6. 参考链接
   如有错误,欢迎指正