字符串进阶算法小结
2021-03-02 19:28
阅读：667
标签：class 信息学奥赛 div span 概念 特殊 关于 manacher 时间复杂度 本文参考《信息学奥赛一本通·金牌导航》。 Manacher 算法，经常被称作马拉车，可以以 \(\mathcal{O}(n)\) 的时间复杂度求出字符串关于回文子串一类的问题。 首先举个例子，设字符串 \(s=\texttt{bbdkd}\)。 在这里面，有偶回文子串 \(\texttt{bb}\)、奇回文子串 \(\texttt{dkd}\)，在计算的过程中还要对奇偶问题进行讨论太过于麻烦，所以可以在每个字符之间加入特殊字符（首尾特殊字符可以作边界）： 再设 \(R_i\) 表示以第 \(i\) 位字符为中心的最长回文的半径。对应上面的 \(s‘\) 可以得到： 字符串进阶算法小结 标签：class 信息学奥赛 div span 概念 特殊 关于 manacher 时间复杂度 原文地址：https://www.cnblogs.com/GJY-JURUO/p/14403298.html前言：
正文：
Manacher 算法：
概念：
介绍：
\[s‘=\texttt{\$#b#b#d#k#d#@}
\]
\[R=\{1,2,3,2,1,2,1,4,1,2,1\}
\]
评论
亲，登录后才可以留言！