简介 朴素的算回文串的办法一般是O（n ^ 2） 或 O（n ^ 3）的。而Manacher发明的马拉车算法能将空间复杂度和时间复杂度均优化到O（n）的线性。 具体算法过程是： 1、将字符串中加入# 如 abcde -> ##a#b#c#d#e 举个例子 一个字符串s = abbahopxpo，转换为$#a#b#b#a#h#o#p#x#p#o#（这里的字符 $ 只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#…
