首页 > 其他分享 >关于 manacher 的一个小细节

关于 manacher 的一个小细节

时间:2022-11-06 17:35:07浏览次数:95  
标签:c# manacher 分隔符 hw 减一 细节 关于 ans

在该算法中,我们需要用到一个数组 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

相关文章