参考资料与图片来源
我觉得这个博客讲的不好，他只讲看规律得到的结论，原因却不说，怪。
算法思路
对于长度可能为奇可能为偶的情况，首先要预处理字符串，在每个字符左右增加一个无关字符 #。
这样字符串的长度就固定为奇数了。
接下来我们选定一个字符，以他为中心向左右扩展，求回文半径，如果只有其一个字符，半径为 \(1\)。
如：
\[\begin{aligned} &\text{# 1 # 2 # 2 # 1 # 2 # 2 #}\\ &1\ \ 2\ \ 1\ \ 2\ 5\ \ 2\ \ 1\ \ 6\ 1\ \ 2\ \ 3\ \ 2\ \ 1 \end{aligned} \]或者：
为什么要求回文半径？
以上面的 \(22122\) 为例子，其中心的 \(1\) 回文半径是 \(6\)，而该字符串原本的长度是 \(5\)。
这是一个普遍的规律：\(\left\lceil\frac{\text{原字符串长度}}{2}\right\rceil=\)回文中心左（包括回文中心）的字符串长度（即字符串回文半径）\(=\)回文中心左增加的 # 数。
设字符串回文半径长度为 \(P\)，那么加了#的字符串长度就为 \(2\times P-1\)，而分隔符是 \(P\) 个，故原字符串长度 \(T=2\times P-1-P=P-1\)
故，字符串回文长度=回文半径长度 \(-1\)。
现在我们就有了字符串长度，而由于第一个和最后一个字符都是#且需要搜索回文，所以为了防止越界，我们在前面加上一个非回文字符%，而后面就不用加了，因为结尾一定有一个字符'/0'。
（tips：越界例如：o 在 #b#o#b# 中的位置是 \(3\)，但是半径是 \(4\)，相减得起点为 \(-1\)，越界）
具体实现
最后就是如何求解我们的回文半径数组 \(P\) 的问题。
设 \(mi\) 是 \(i\) 位置之前回文长度能到达最远的右端点的回文串的重心位置，\(R\) 是最大回文串的能达到的右端点的值。
- 若 \(i\leq R\)，我们可以找到 \(i\) 以 \(mi\) 为对称点对称到左边的位置 \(j=2\times mi-i\)。
- 若 \(P_j<R-i\)，那么证明 \(i\) 的回文没有超出 \(R\) 的边界，\(P_i=P_j\)。
- 若 \(P_j\geq R-i\)，超出 \(R\) 的部分一个个和前面匹配。
- 若 \(i>R\)，那有什么办法，一一匹配呗。
时间复杂度 \(O(n)\)。
有代码：
Miku's Code
string Manacher(string s){
string res="$#";
for(int i=0;i<s.size();++i){
res+=s[i];
res+="#";
}
/*改造字符串*/
/*数组*/
vector<int> P;
for(rg i=0;i<=res.size();++i) P.push_back(0);
int mi=0,right=0; //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值
int maxLen=0,maxPoint=0; //maxLen为最大回文串的长度，maxPoint为记录中心点
for(int i=1;i<res.size();++i){
if(right>i) P[i]=min(P[2*mi-i],right-i);
else P[i]=1;
while(res[i+P[i]]==res[i-P[i]]) ++P[i];
if(right<i+P[i]){
//超过之前的最右端，则改变中心点和对应的最右端
right=i+P[i];
mi=i;
}
if(maxLen<P[i]){
//更新最大回文串的长度，并记下此时的点
maxLen=P[i];
maxPoint=i;
}
}
return s.substr((maxPoint-maxLen)/2,maxLen-1);
//在原串中提取最大回文子串
}
然后将函数返回值改成 int 和 \(maxLen-1\) 就能切掉洛谷的模板题。
（似乎我过这道题的时候数据过水，但是新的 hack 并没有卡掉咱捏）
例题
Sonya and Matrix Beauty
题面翻译
题目描述
一句话题意：给定一个 \(n \times m\) 的字符矩阵，请求出有多少个子矩阵在重排子矩阵每一行的字符后，使得子矩阵的每行每列都是回文串。
Sonya 最近过了生日，她收到一个 \(n \times m\) 的字符矩阵。
我们称一个子矩阵是美丽的，当且仅当在重新排列这个子矩阵每一行的字符后，使得这个子矩阵的每一行每一列都是回文串。
Sonya 想要知道这个矩阵中有几个子矩阵是美丽的。
输入格式
第一行两个整数 \(n,m\)，意义如上文所述。
接下来 \(n\) 行一行 \(m\) 个字符，表示这个子矩阵每一行的字符。
输出格式
一行一个整数，表示美丽的子矩阵数目
数据范围
对于 \(1 \leq m,n \leq 250\)
题目描述
Sonya had a birthday recently. She was presented with the matrix of size $ n\times m $ and consist of lowercase Latin letters. We assume that the rows are numbered by integers from $ 1 $ to $ n $ from bottom to top, and the columns are numbered from $ 1 $ to $ m $ from left to right.
Let's call a submatrix $ (i_1, j_1, i_2, j_2) $ $ (1\leq i_1\leq i_2\leq n; 1\leq j_1\leq j_2\leq m) $ elements $ a_{ij} $ of this matrix, such that $ i_1\leq i\leq i_2 $ and $ j_1\leq j\leq j_2 $ . Sonya states that a submatrix is beautiful if we can independently reorder the characters in each row (not in column) so that all rows and columns of this submatrix form palidroms.
Let's recall that a string is called palindrome if it reads the same from left to right and from right to left. For example, strings $ abacaba, bcaacb, a $ are palindromes while strings $ abca, acbba, ab $ are not.
Help Sonya to find the number of beautiful submatrixes. Submatrixes are different if there is an element that belongs to only one submatrix.
输入格式
The first line contains two integers $ n $ and $ m $ $ (1\leq n, m\leq 250) $ — the matrix dimensions.
Each of the next $ n $ lines contains $ m $ lowercase Latin letters.
输出格式
Print one integer — the number of beautiful submatrixes.
样例 #1
样例输入 #1
1 3
aba
样例输出 #1
4
样例 #2
样例输入 #2
2 3
aca
aac
样例输出 #2
11
样例 #3
样例输入 #3
3 5
accac
aaaba
cccaa
样例输出 #3
43
提示
In the first example, the following submatrixes are beautiful: $ ((1, 1), (1, 1)); ((1, 2), (1, 2)); $ $ ((1, 3), (1, 3)); ((1, 1), (1, 3)) $ .
In the second example, all submatrixes that consist of one element and the following are beautiful: $ ((1, 1), (2, 1)); $ $ ((1, 1), (1, 3)); ((2, 1), (2, 3)); ((1, 1), (2, 3)); ((2, 1), (2, 2)) $ .
Some of the beautiful submatrixes are: $ ((1, 1), (1, 5)); ((1, 2), (3, 4)); $ $ ((1, 1), (3, 5)) $ .
The submatrix $ ((1, 1), (3, 5)) $ is beautiful since it can be reordered as:
<br></br>accca<br></br>aabaa<br></br>accca<br></br>In such a matrix every row and every column form palindromes.
解题
睡个觉先，等我睡醒就写
标签：子串,字符,Manacher,矩阵,leq,字符串,回文,样例 From： https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/Manacher_is-not_horse-pull-a-car_written-b