关于PAM做法的疑惑

P4287 [SHOI2011] 双倍回文

New_hope @ 2024-06-01 14:13:12

求不过半的指针 p_i 时，是什么原因导致一下代码会 T 一个点（其他都过了），或者说跳得有什么问题。

int p(fail[tot]);
while (len[p]*2 > len[tot]) p = fail[p];
bin[tot] = p;

by 阿尔萨斯 @ 2024-09-12 21:00:11

我有个有趣的想法，不知道可不可行（因为我还没写），就是可不可以写个倍增来令暴力跳变成log级别的跳，最终时间复杂度到达nlogn

by 阿尔萨斯 @ 2024-09-12 21:12:26

刚AC了，发现我写的暴力跳确实会TLE一个点，写倍增就过了

|