Warning: session_start(): open(/tmp/sess_313b6f73c4ff8214bdb8812f6d727cf7, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:字符串 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:字符串

Manacher

原串插入特殊字符,长度变为 $2\times n+1$。
记录当前最右回文边界 $r$ 以及对应中心点 $c$,第 $i$ 个中心点以对称点长度为起始点出发暴力匹配,可证 $r$ 单调递增或 $O(1)$ 直接得到答案。
最终最长回文串长度为 $\max_{0\leq i<len}{p_i-1}$
时空间复杂度 $O(n)$

2020-2021/teams/looking_up_at_the_starry_sky/shenzhonghai/字符串.txt · 最后更改: 2020/10/10 22:31 由 x342333349