0%

Manacher算法

待填坑,忘了

情景引入与分析

最长回文子串问题: 给定一个字符串S,求出他的最长回文子串。
设S串长度为N

朴素算法,对于S的所有子串判断它是否为回文串。枚举字符串N^2,所以这个很朴素,时间复杂度O(N^3)

一种稍微好一点的想法是,对于每个中心,尝试向两边扩展,得到回文串。枚举中心为2N-1 , 每次枚举的时间复杂度最坏为N/2,所以总时间复杂度为O(N^2)

何以改进:

  1. 之前得到的每个中心的结果,在之后新的中心扩展的过程中并没有得到利用。
  2. 在枚举中心的时候,长度为奇和长度为偶在最开始的处理有些不同

Manacher算法

(1) 解决长度奇偶性带来的对称轴位置问题

每两个字符中间加入一个相同的字符(原串中没有)使得原串变为奇数长度的串。那么回文中心就不会再是间隙而是有具体的位置。
并且旧子串与新子串的回文性不受影响

(2) 利用之前得到的信息