前情提要,参考资料：Manacher - OI Wiki

用心制作，来理解Manacher算法吧（力扣，最长回文子串）_哔哩哔哩_bilibili

一、背景

        对于一个长度为n的字符串s，请找到所有对 ( i, j ) 使得子串 s[i...j] 为一个回文串。当 t = t_rev 时，字符串 t 是一个回文串(t_rev 为 t 的反转字符串)。

        若使用朴素算法(即对于选中区间 (i, j) 的中心  mid, 存在回文串就将 ans 加1)，显然算法时间复杂度为 O(n²)。

        其他算法也不错，比如字符串哈希 (O(n log n))，后缀数组LCA O(n)。

二、基本概念

        介绍：Manacher算法，用于在给定字符串中查找最长回文子串。通过利用回文串的对称性，将时间复杂度优化到 O(n)，相比朴素算法（O(n²)或 O(n³)）具有显著的性能优势。

        原理：将奇数长度和偶数长度的回文子串统一处理，并利用已知的回文信息减少不必要的比较。(简白明了就是在字符串中穿插特殊字符，下面讲预处理)

三、算法过程讲解

        1.字符串预处理：各大题目中可能出现奇数串、偶数串(没事，Manacher来帮你)，对于我们要找的对称中心需要奇数长度，在每个字符之间插入特殊字符即可(如  # )。怕越界也可以添加边界字符(尽量用不同的字符，如 $ 和 ^ )，遍历到该字符就终止。

                ed: s = "aba"，预处理 ——  "$#a#b#^"。

        2.关键变量：

        ° P数组：用于存储每个位置为中心的最长回文的半径（扩展长度）。例如，P[i]表示以位置i为中心的最长回文的半径。

        ° C：当前已知最长回文的中心位置。

        ° R：当前已知最长回文的右边界。

        3.回文半径数组：Manacher的核心数组，建立一个数组 P 来 记录每个位置的回文半径，p[i]即表示以 i 为中心的最长回文串的半径。(这个半径是指从中心位置 i向两边扩展的字符数，不包括中心位置本身)。这使得算法实现了线性时间复杂度。

          回文半径数组详解(难就难在这)、                  

            具体作用

        (1) 记录回文信息：P[i]记录了以位置 i为中心的最长回文子串的半径，这使得我们可以在遍历过程中快速找到最长回文子串。

        (2) 利用对称性：当当前位置 i在已知的右边界R内时，可以利用对称点 mir（即2 * C - i，其中 C是已知回文串的中心）的回文半径 P[mir]来初始化 P[i]。这减少了不必要的比较，提高了算法的效率。

        (3) 扩展回文串：对于每个位置 i，算法尝试从 P[i]开始扩展回文串，直到无法匹配为止。这确保了我们总是从已知的回文信息出发，尽可能地利用已有的结果。

        (4) 更新最大回文串：在遍历过程中，算法不断更新最大回文半径 maxLen及其对应的中心位置 mir。这使得我们可以在遍历结束后立即找到最长回文子串。

        ED:

        假设我们有字符串s = "abba"，预处理后的字符串t = "$#a#b#b#a#^"。回文半径数组p的计算过程如下：        

i	P[i]	回文中心	回文串
1	0	-	-
2	1	a	a
3	2	#	a#b#b#a
4	1	b	b#b
5	0	-	-

通过这个过程，我们发现最大回文半径为 2，对应的中心位置为 3。因此，最长回文子串为"abba"。 (注意边界字符的处理)

        4.利用对称性: 

        算法维护一个“右边界最远的回文串”（记为(l, r)），并利用其对称性来减少计算：

        ° 如果当前中心 i在右边界 r内，则 p[i]可以初始化为 min(r - i, P[j])，其中 j是 i关于(l, r)的对称点。

        ° 如果 i超出右边界，则从 P[i] = 0开始扩展。

        5.扩展回文串：

                对于每个回文中心 i，算法尝试扩展回文串，直到无法匹配为止。如果扩展后的右边界i + P[i]超过了当前的 r，则更新右边界和中心。

//l = i - (P[i]+1), r = i + (P[i]+1), 
//扩展回文串(0 ≤ l,r < n; t[l] == t[r])
while(i - (P[i]+1) >= 0 && i + (P[i]+1) < n && t[i - (P[i]+1)] == t[i + (P[i]+1)]){
    P[i]++;//回文半径++
}

        6.记录最长回文子串: 在遍历过程中，算法记录最大回文半径及其位置，并最终提取最长回文子串。

        7.复杂度分析：Manacher算法在回文字符串中心进行扩展，扩展两次(一次向左，一次向右)，时间复杂度为 O(n)。空间上主要是预处理字符串和会问数组 P，其空间复杂度也为 O(n)。

 

四、总结

        Manacher算法以独特的预处理方式和回文数组出名，以添加特殊字符处理字符串奇偶，以回文半径数组处理回文串。算法复杂度占优，值得入手。

课下习题：P3805 【模板】manacher - 洛谷

                P4555 [国家集训队] 最长双回文串 - 洛谷

模板：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//为原字符串添加'#'
string add(const string& s){
	string t = "#";
	for(char i : s){
		t += i;
		t += '#';
	}
	return t;
}

//Manacher算法
int manacher(const string& s){
	string t = add(s);//预处理字符串
	int n = t.size();
	vector<int> P(n, 0);//回文半径数组
	int C = 0, R = 0;//对应回文字符串的中心、最右回文边界
	int num = 0;//记录长度
	for(int i = 0; i < n; ++i){
		if(i < R){
			int mir = C*2 - i;
			P[i] = min(P[mir], R - i);
		}
		//扩展回文串(0 ≤l,r < n; t[l] == t[r])
		while(i - (P[i]+1) >= 0 && i + (P[i]+1) < n && t[i - (P[i]+1)] == t[i + (P[i]+1)]){
            P[i]++;
        }
		if(i+P[i] > R){//更新右边界和中心
			C = i;
			R = i+P[i];
		}
		num = max(num, P[i]);
	}
	return num;
}

int main(){
	string s;
	cin >> s;
	int ans = manacher(s);
	printf("%d\n", ans);
	return 0;
}