0x00 摘要
“马拉核弹”算法由 SXHT 同学（2009~今）发明，并在 2024 年 11 月于某不知名学校机房内正式公布。该算法基于 1975 年发明的 Manacher 算法，并将其推广至对称正方形问题。
原文链接与密码：sunxuhetai2009。
关键词：Manacher 算法 信息学 对称正方形
0x01 缘由
先来看这道题目：
给定一个 \(n\) 行 \(m\) 列的矩阵，求矩阵中上下对称且左右对称的正方形子矩阵的个数。
这道题可以应用二维哈希实现，时间复杂度 \(O(n^2 \text{log} n)\)；但马拉核弹算法提供了另一种可能性。
0x02 解释
标签：Mana,Nuclear,矩阵,马拉,正方形,算法,核弹,对称 From： https://www.cnblogs.com/chenaknoip/p/18530993嗯哼！单调性——显然有若大正方形对称，则被大正方形包含的小正方形对称
二分是非常不错的选择呢！进一步，二分正方形边长
然后就是快乐的枚举中心点环节
剩余的操作类似于……，只不过换成了二维矩阵
同样需要注意如下情况……
- 对于奇数阶和偶数阶的两种情况，要分开处理哦！
- 上下翻转和左右翻转后的结果都需要比对成功才算回文矩阵