求本题 manacher 的 O(n) 做法的证明

P4287 [SHOI2011] 双倍回文

Piwry @ 2021-01-25 14:19:43

我在题解区找到了三篇：A, B, C（貌似都不完全一致）

或者您直接给出一种全新的做法（O(n)）也行 \kk

by 小粉兔 @ 2021-01-25 14:28:37

这个题用 PAM 做到 \mathcal O (n) 是很简单的吧

by 小粉兔 @ 2021-01-25 14:29:40

和这个题的实现很类似吧

https://www.cnblogs.com/PinkRabbit/p/IOI2021Homework1.html#og-virus-synthesis

by 小粉兔 @ 2021-01-25 14:29:59

https://www.luogu.com.cn/problem/P4762

by Stinger @ 2021-01-25 14:30:04

达成成就：捕捉兔队

by 小粉兔 @ 2021-01-25 14:31:04

https://www.luogu.com.cn/blog/Flying-Bird/p4287-shoi2011-shuang-bei-hui-wen-ti-xie 这个本题的题解不是解释清楚了吗？

by Piwry @ 2021-01-25 14:39:50

@小粉兔

Orz

谢谢XD

不过我发这个帖子主要原因是对用 manacher 做到 O(n) 的那几篇题解感到很迷惑...（

by Forever1507 @ 2021-01-25 14:56:56

成就：捕捉粉

\\

 \\_

.---(')

o( )-\