在该算法中,我们需要用到一个数组 hw[i] ,代表 i 的最大回文半径。而且这个半径不包括 i 本身(若串为 ccc 则 hw 为 1)。
这时最终答案为最大的 hw 减一。
为什么要减一呢?最终的串只有两种形式
c#c#c# 或 #c#c#c#c# 。即中间为 # 或中间为 c (#为加入的分隔符,c为原字符串中的一个字符)
可以数一下,这两种情况若设最终答案为 \(ans\) ,则总会有 \(ans + 1\)个分隔符。
所以可得 \(2hw + 1 = ans + (ans + 1)\)。
转换后可以得到 \(ans = hw - 1\) 。
标签:c#,manacher,分隔符,hw,减一,细节,关于,ans From: https://www.cnblogs.com/closureshop/p/16863106.html