On求最长回文子串
众所周知,manacher可以On求最长回文子串,但是神奇的字符串hash也可以做到求最长回文串。
步骤:
- 预处理字符串,类似于manacher,每两个字符中间插入‘#’,因为这样才能枚举中心。
- 预处理正哈希和逆哈希,如果正哈希[l,r]==逆哈希[l,r],说明两个字符串相同。
- 枚举回文中心,二分求回文半径。
可以看出,时间复杂度是$O(nlogn)$,代码如下:
1 |
|
这**博主怎么骗人啊,不是On复杂度吗。
其实,不需要二分,直接记录当前最长半径,下次枚举直接使用从之前的最大半径开始即可。
$O(n)$代码:
1 | unsigned long long order1[2000100], order2[2000100]; |