标签: manacher

1 篇文章

浅谈 Manacher
基本概念 回文子串:字符串中反转后与反转前相同的子串。 最长回文子串:字符串中长度最大的回文子串。 第 $i$ 位回文半径:以字符串第 $i$ 位为中心的回文子串的最大长度的一半。 在处理回文子串的问题时,一般需要求出字符串每一位的回文半径。 为了避免奇偶讨论和边界问题,我们可以在每一位字符两侧添加同一个特殊字符,在字符串的首尾各添加一个不同的特殊…