Manacher 算法

一、暴力扩展的痛点：为什么每次都要“从零起步”？

场景：给定一个长度为 $n$ 的字符串 $S$，找出其中最长的回文子串。

直觉解法（中心扩展法）： 回文串是左右对称的。既然对称，最自然的思路就是枚举“对称中心”，然后双指针向两侧同时伸手比对字符：如果左右字符相等，回文长度就加 2，继续往外扩；一旦遇到字符不同或撞到边界就停下。

但只要一写代码，你马上就会撞上两个令人极其头疼的痛点：

1. 奇偶回文的物理断层

• 观察奇数回文 a b a c a b a：它的对称中心非常明确，正好落在正中间的字符 c 上。
• 但再看偶数回文 a b b a：它的对称中心在哪里？它根本不在任何一个字符上，而是悬在中间两个 b 之间的“空隙”里！
• 如果你只枚举字符作为中心，所有的偶数长度回文将被全部漏掉。

2. 暴力扩展的时间灾难（$O(n^2)$）

在长串上，中心虽然只有 $O(n)$ 个，但每个中心向外扩展的步数却无法保证。

拿极端串 a a a a a a 来说：每一个位置作为中心都能向外扩很远。在前面的中心辛辛苦苦比对过的字符，换到下一个中心时，暴力算法却彻底失忆，不得不把相同的字符重新比对一遍。最坏情况下总比对次数会迅速退化为 $O(n^2)$。面对信奥竞赛中 $n \ge 10^6$ 甚至 $10^7$ 的极限数据，暴力做法会瞬间超时（TLE）。

降维设问：回文具有完美的对称性。我们在左边已经探测过的信息，能不能直接“翻个面”借给右边，省去重复比对的无效劳动？

这正是 Manacher 算法的核心灵魂。插入 # 等分隔符也能统一处理奇偶回文；本讲选择直接记录两种半径，沿用原串的 0-based 下标，方便后面用区间坐标查询。

二、物理意义明确：两种回文半径（奇数中心与偶数空隙）

为了让计算机记录下每个中心的能力上限，我们定义两个核心的“灵魂数组”。全文严格采用 0-based 索引，区间 $[L, R]$ 均为双端闭区间。

1. 奇数回文的灵魂数组：d1[i]

• 物理意义：以字符 s[i] 为中心，向外扩展出的最大奇数回文的半径（中心字符本身算作第 1 层）。
• 底线：单个字符本身就是一个长度为 1 的合法奇回文，因此每个位置的天然半径至少为 $1$。
• 区间与长度推导： 若 d1[i] = k，表示以 $i$ 为中心左右各伸出了 $k-1$ 步。
  • 覆盖区间：$[i - k + 1,\ i + k - 1]$
  • 回文长度：$(k - 1) + 1 + (k - 1) = \mathbf{2k - 1}$

手推验证：对字符串 a b a c a b a（长度为 7）：

• 在 $i=1$ 处（字符 b）：向外扩 1 层得到 a b a，半径为 $2$，长度为 $2 \times 2 - 1 = 3$。
• 在 $i=3$ 处（字符 c）：向外扩 3 层直接通关整个字符串，半径为 $4$，长度为 $2 \times 4 - 1 = 7$。

2. 偶数回文的灵魂数组：d2[i]

• 物理意义：以字符 s[i-1] 与 s[i] 之间的空隙为中心，向外最多能成功配对的字符对数。
• 坐标规约：空隙不是字符，怎么用下标存储？我们规定：用空隙右侧字符的下标 $i$ 来代表该空隙！
• 底线：如果左右相邻两个字符根本不相等，配对对数就是 $0$。特别地，字符串最左侧外面没有字符，定义 d2[0] = 0。
• 区间与长度推导： 若 d2[i] = k，表示以空隙为中心成功配对了 $k$ 对字符。
  • 覆盖区间：$[i - k,\ i + k - 1]$
  • 回文长度：$\mathbf{2k}$

手推验证：对字符串 a b b a：

• 在空隙 $2$ 处（即 s[1]='b' 与 s[2]='b' 之间的缝隙）：
  • 第一层：s[1] 与 s[2] 匹配成功（配对数 1）；
  • 第二层：s[0] 与 s[3] 匹配成功（配对数 2）。
  • 因此 d2[2] = 2，覆盖区间为 $[2-2,\ 2+2-1] = [0, 3]$，回文长度为 $2 \times 2 = 4$。
  • 其余位置均无法配对，故 d2 数组为 [0, 0, 2, 0]。

三、核心魔法：把已知大回文当作“镜子”

现在我们明确了成绩单的定义。Manacher 算法的威力，就在于它从左向右扫描每个中心时，会随身维护一把“具有庇护能力的巨伞”。

1. 领地守护者：最右回文区间 $[l, r]$

在算法推进过程中，我们时刻维护一个已经探测到的回文区间 $[l, r]$。

核心心法：$[l, r]$ 记录的不是当前最长的回文串，而是右端点 $r$ 伸得最远的回文串！ 为什么？因为我们是从左往右扫描的，只有把右边界 $r$ 推得越远，后面的新中心才越有可能被罩在 $[l, r]$ 内部，从而白借信息。

2. 奇数中心的信息继承与“安全红线”

假设当前我们要计算中心 $i$ 的奇数半径 d1[i]：

场景 A：当前中心 $i > r$（沦为法外孤岛）

当前中心已经超出了目前所有探明回文的右边界 $r$。没有任何前人经验能帮到它，没有任何信息可借。

• 动作：从底线 $k = 1$ 开始，老老实实执行 while 循环向两边逐个字符暴力比对。

场景 B：当前中心 $i \le r$（处于大回文的绝对庇护之下）

此时 $i$ 完整落在 $[l, r]$ 内部。根据回文串的对称特性，我们在 $[l, r]$ 内部找一个与 $i$ 关于中心对称的镜像位置 $j$。 由中点公式可知：$\frac{j + i}{2} = \frac{l + r}{2} \implies \mathbf{j = l + r - i}$。

因为 $j$ 在 $i$ 的左边，我们在之前的循环中早已经把 $j$ 的底细探得一清二楚（d1[j] 已算好）。大回文 $[l, r]$ 既然是对称的，那么在 $j$ 处开出的“回文之花”，照理说在 $i$ 处也能一比一复刻一份！

但能直接无脑写 k = d1[j] 吗？绝对不能！ 这里存在一条生死攸关的“安全红线”：

为什么必须用 $\min$ 强行截断？（物理安全底线）

• $j$ 处的回文花朵可能开得非常大，它的左花瓣甚至一直延伸到了区间左界 $l$ 的外面。
• 但是，母体大回文 $[l, r]$ 仅仅保证了自己在 $[l, r]$ 范围之内的字符是完全对称的！
• 一旦超出边界，右侧 $r$ 以外的字符世界究竟长成什么样，母体根本一无所知！
• 从中心 $i$ 到右边界 $r$ 包含中心在内，最多只有 $r - i + 1$ 个字符。因此，只有 $r - i + 1$ 步之内的信息是 100% 免检合法的。超出 $r$ 的未知领地，必须停下来，交给接下来的 while 循环去真正比对。

手推验证：abacaba 中的信息借用

当中心处理完 $i=3$ 时，整串构成大回文，维护的区间被更新为 $[l, r] = [0, 6]$。

• 移到 $i=4$：镜像为 $j = 0 + 6 - 4 = 2$。已知 $d1[2]=1$，右边界剩余 $6 - 4 + 1 = 3$。取 $\min(1, 3) = 1$。直接继承 $k=1$，向外比对 $s[3]$ 与 $s[5]$（即 c 与 b），不相等，扩展立即终止！
• 移到 $i=5$：镜像为 $j = 0 + 6 - 5 = 1$。已知 $d1[1]=2$。右边界剩余 $6 - 5 + 1 = 2$。取 $\min(2, 2) = 2$。直接白嫖 $k=2$，连字符都不用比，就继承了半径 2！继续向外比对已越界，最终 d1[5]=2。

3. 偶数空隙的镜像计算（半格位移的精妙修正）

偶数空隙也是同样的镜像借力思想，但所有初学者在这里都会栽跟头：空隙的镜像坐标究竟怎么算？

• 我们对空隙的编号用的是它右侧字符的下标。因此，编号为 $i$ 的空隙，它的物理真实坐标在 $i - 0.5$ 处。
• 整个大区间 $[l, r]$ 的物理中心在 $\frac{l + r}{2}$ 处。
• 设它翻过去的镜像空隙物理坐标为 $pos$，则有：
  $$\frac{pos + (i - 0.5)}{2} = \frac{l + r}{2} \implies pos = l + r - i + 0.5$$
• 按照规约，空隙编号取其右侧字符下标（即物理坐标加 $0.5$）：
  $$j = pos + 0.5 = (l + r - i + 0.5) + 0.5 = \mathbf{l + r - i + 1}$$

教练敲黑板：这就是偶数回文镜像公式中那个看似诡异的 +1 的物理来源！少了这个 +1，你的对称镜子在物理空间上就照偏了整整半格，直接全盘皆输。

偶数扩展步骤：

1. 若 $i > r$，没有庇护，从 $k = 0$ 开始；
2. 若 $i \le r$，安全继承：$k = \min(d2[l + r - i + 1],\ r - i + 1)$；
3. while 逐层考察待配对字符：左边为 $s[i - k - 1]$，右边为 $s[i + k]$；
4. 扩展结束后更新右边界：当前回文覆盖 $[i - k,\ i + k - 1]$，若 $i + k - 1 > r$，则令 $l = i - k,\ r = i + k - 1$。

4. 纯 aaaaaa 手推：彻底看清常数跳步机制

拿最能卡死暴力的全相同字符串 a a a a a a，单看奇数回文的处理过程：

关键细节剖析：

• 在中心 3：直接白嫖了半径 2，从下一层（下标 1 与 5）直接开比起，避免了从中心从头扩展。
• 在中心 4：镜像 2 的半径虽然高达 3，但此时 $r - i + 1 = 5 - 4 + 1 = 2$。安全红线死死拉住了它，防止它狂妄越界。正是这个取 $\min$，从逻辑层面确保了算法 100% 的正确性。

四、复杂度证明：为什么套了 while 依然是严格 $O(n)$？

初看代码，外层 for 循环里面赫然嵌套着一个 while 循环，许多同学会下意识认为这是 $O(n^2)$。

物理视角的“单向开荒模型”： 我们要把目光聚焦在右边界 $r$ 的运动轨迹上。while 内部的比对尝试，只有两种命运：

1. 比对失败：当前中心碰到了不相等的字符或撞到边界，while 循环立即终止。既然每个中心只会终止一次，那么在整个算法生命周期中，所有比对失败的总次数加起来最多只有 $n$ 次。
2. 比对成功：只有当继承的初始半径已经触及或越过了已知的右边界 $r$（即 $i + k - 1 \ge r$）时，才有可能比对成功并执行 k++。而每一次成功的 k++，都实打实地将右边界 $r$ 向右拓宽至少 1 格！ 由于字符串长度只有 $n$，$r$ 只能单调向右推进，最多从 0 推进到 $n-1$，永远不可能回头。因此，比对成功的总次数绝对不会超过 $n$ 次。

成功最多 $n$ 次，失败最多 $n$ 次，总操作次数被牢牢锁死在 $2n$ 次以内！ 奇数一遍跑满 $O(n)$，偶数一遍跑满 $O(n)$，整体是货真价实、无可挑剔的严格 $\mathbf{O(n)}$。

五、核心模板与实战代码：洛谷 P3805 最长回文子串

💡 【实战例题：洛谷 P3805 【模板】manacher】

• 输入格式：输入一行由小写英文字母组成的字符串 $S$。
• 输出格式：输出一个整数，表示 $S$ 中最长回文子串的长度。
• 数据范围：$1 \le |S| \le 1.1 \times 10^7$。

1. 竞赛常数与空间极限优化

在 P3805 中，数据范围高达惊人的 $1.1 \times 10^7$。

• 内存考量：在 32 位 signed int 下，数组每个元素占 4 字节，一个千万级数组大约占用 $44\text{ MB}$。如果盲目使用 #define int long long，数组直接翻倍飙升到近 $88\text{ MB}$。由于题目中回文长度和下标绝对在 $2 \times 10^9$ 以内，这里刻意保持 32 位 int，以压榨出极致的内存与 CPU 缓存性能。
• 空间复用黑科技：既然我们只求全局最大的回文长度，奇数回文半径在跑完第一轮后就不再需要保留。我们可以让奇数与偶数扫描完全共用同一个全局数组 d[N]！
  • 为什么偶数扫描不会读到残存的奇数数据？
  • 因为偶数扫描查镜像时，$j = l + r - i + 1 < i$。镜像位置 $j$ 一定在当前中心 $i$ 的左侧，在跑偶数这一轮时，位置 $j$ 早已被写入了最新的偶数半径！

#include<bits/stdc++.h>
using namespace std;
const int N=11000005;

string s;
int d[N];
int n,ans;

void solve(){
	cin>>s;
	n=s.size();
	
	// 1. 第一遍：处理所有奇数回文中心
	int l=0,r=-1;
	for(int i=0;i<n;i++){
		// 处于已知回文内则取镜像与右边界的交集，否则初始半径为 1
		int k=(i>r?1:min(d[l+r-i],r-i+1));
		
		// 暴力尝试向外扩展
		while(i-k>=0 && i+k<n && s[i-k]==s[i+k]) k++;
		
		d[i]=k;
		ans=max(ans,2*k-1); // 奇数长度为 2k - 1
		
		// 若右端点进一步被推开，则更新维护区间
		if(i+k-1>r){
			l=i-k+1;
			r=i+k-1;
		}
	}
	
	// 2. 第二遍：处理所有偶数空隙中心（直接复用 d 数组）
	l=0,r=-1;
	for(int i=0;i<n;i++){
		// 偶数镜像注意带上 +1；无庇护时初始配对数为 0
		int k=(i>r?0:min(d[l+r-i+1],r-i+1));
		
		// 考察左右两侧对称字符
		while(i-k-1>=0 && i+k<n && s[i-k-1]==s[i+k]) k++;
		
		d[i]=k;
		ans=max(ans,2*k); // 偶数长度为 2k
		
		if(i+k-1>r){
			l=i-k;
			r=i+k-1;
		}
	}
	
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

提取具体子串技巧：若题目要求输出最长回文子串本身，只需在 ans 被更新时顺便记录最长子串的起始下标：

• 奇数回文的起点为 i - k + 1；
• 偶数回文的起点为 i - k。 扫描完毕后，直接调用 s.substr(start_pos, ans) 即可，严禁在循环内做字符串拷贝！

六、进阶模型：$O(1)$ 极速判定任意区间是否为回文

💡 【实战例题：静态子串回文在线查询】

• 输入格式：
  • 第一行输入一个字符串 $S$；
  • 第二行输入一个整数 $q$，表示询问次数；
  • 接下来 $q$ 行，每行给出两个整数 $L, R$（0-based 索引，保证 $0 \le L \le R < |S|$）。
• 输出格式：对于每次询问，如果子串 $S[L..R]$ 是回文串输出 Yes，否则输出 No。
• 数据范围：$1 \le |S| \le 10^6$，$0 \le q \le 2 \times 10^5$。

1. 破题引导：中心与半径的几何包容性

不要试图对每次询问去走一遍比较，那将是 $O(q \cdot n)$ 的超时做法。

注意到区间 $[L, R]$ 的长度 $\text{len} = R - L + 1$：

• 它的几何中心位置是绝对固定死的。
• 只要判断该几何中心所能达到的最大回文半径，能否把区间 $[L, R]$ 完整罩住！

1. 若 $\text{len}$ 为奇数：

   • 几何中心在字符上：$c = L + \text{len} / 2$（等价于 $(L+R)/2$）。
   • 该区间从中心往单侧需要辐射 $\text{len} / 2$ 步，加上中心自己，需要的最小半径是 $\text{len}/2 + 1$。
   • 判定标准：$\mathbf{d1[c] \ge len / 2 + 1}$。

2. 若 $\text{len}$ 为偶数：

   • 几何中心在空隙上：空隙右侧字符下标正好也是 $c = L + \text{len} / 2$（等价于 $(L+R+1)/2$）。
   • 该区间需要成功配对 $\text{len} / 2$ 对字符。
   • 判定标准：$\mathbf{d2[c] \ge len / 2}$。

物理意义点睛：为什么这里用 >= 而不是 ==？ 因为一个大的回文串，以其中心向内收缩出来的所有同心子串，全部必然都是合法回文串！所以只要最大半径能够“覆盖”询问区间即可。

这次因为随时需要应对奇偶查询，我们需要完整保留两个半径数组 d1 与 d2。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;

string s;
int d1[N],d2[N];
int n,q;

void solve(){
	cin>>s;
	n=s.size();
	
	// 预处理奇数回文半径
	int l=0,r=-1;
	for(int i=0;i<n;i++){
		int k=(i>r?1:min(d1[l+r-i],r-i+1));
		while(i-k>=0 && i+k<n && s[i-k]==s[i+k]) k++;
		d1[i]=k;
		if(i+k-1>r){
			l=i-k+1;
			r=i+k-1;
		}
	}
	
	// 预处理偶数回文半径
	l=0,r=-1;
	for(int i=0;i<n;i++){
		int k=(i>r?0:min(d2[l+r-i+1],r-i+1));
		while(i-k-1>=0 && i+k<n && s[i-k-1]==s[i+k]) k++;
		d2[i]=k;
		if(i+k-1>r){
			l=i-k;
			r=i+k-1;
		}
	}
	
	// O(1) 在线回答每次询问
	cin>>q;
	while(q--){
		int L,R;
		cin>>L>>R;
		int len=R-L+1;
		bool ok=false;
		
		int c=L+len/2; // 极其优美的统一下标计算
		if(len%2==1){
			ok=(d1[c]>=len/2+1);
		}else{
			ok=(d2[c]>=len/2);
		}
		
		cout<<(ok?"Yes":"No")<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 样例验证

输入数据：

abba
4
0 3
1 2
0 2
3 3

输出数据：

Yes
Yes
No
Yes

单测拆解：

• [0, 3]：偶数长 4，中心 $c = 0 + 2 = 2$，查 d2[2] = 2 >= 2，判定为 Yes。
• [1, 2]：偶数长 2，中心 $c = 1 + 1 = 2$，查 d2[2] = 2 >= 1，判定为 Yes。
• [0, 2]：奇数长 3，中心 $c = 0 + 1 = 1$，查 d1[1] = 1 < 2，判定为 No。
• [3, 3]：单字符长 1，中心 $c = 3 + 0 = 3$，查 d1[3] = 1 >= 1，判定为 Yes。

《字符串哈希》第四节第 3 小节与第六节也用正反哈希判断回文；这里预处理半径后同样能 $O(1)$ 回答区间询问，而且没有哈希碰撞风险。

七、进阶模型：基于半径的回文子串计数

问题场景：给定一个字符串，求出其中包含的所有合法回文子串的总数量。注意：位置不同但内容相同的回文串算作独立的多个。

状态含义与推导： 回文串在结构上是层层嵌套的。如果在某个中心位置剥开了一朵半径为 3 的回文花朵（例如长度为 5 的奇数回文 ababa），那么随着半径的收缩，内部的 bab 和单字符 a 也必然是合法的回文串。 这意味着，对于任意一个中心 $i$：

• 它的最大奇数半径为 d1[i]，也就代表着以它为中心，能恰好套出 d1[i] 个不同的奇数回文串。
• 同理，以它的空隙为中心的最大偶数半径（即配对对数）为 d2[i]，说明能套出 d2[i] 个偶数回文串。

关键结论：整个字符串包含的回文子串总数，就是所有中心能辐射出的同心回文数量之和，即 $\sum d1[i] + \sum d2[i]$。

手推小例子： 以字符串 aba 为例。

• 考察奇数半径 d1：
  • i=0（字符 a）：半径 1，贡献 1 个（a）
  • i=1（字符 b）：半径 2，贡献 2 个（b, aba）
  • i=2（字符 a）：半径 1，贡献 1 个（a）
  • 奇数回文总计：$1 + 2 + 1 = 4$ 个。
• 考察偶数半径 d2：
  • 相邻无相同字符，所有空隙扩展配对数均为 0。
  • 偶数回文总计：0 个。 因此总共有 4 个回文子串。

实现要点： 只需在跑完 Manacher 获取 d1 和 d2 后直接累加。

long long ans=0;
for(int i=0;i<n;i++) ans+=1LL*d1[i]+d2[i];

全 a 串的回文子串总数是 $n(n+1)/2$，累加变量要用 long long，不能只看半径数组的范围。

八、选学：前缀/后缀回文判定与最少末尾补齐

场景： 给定一个字符串 $S$，如果你只能在它的末尾添加字符，最少需要添加几个字符，才能让整个新字符串变成一个大回文串？

先修提示：本模型需要你已经完全掌握 d1 和 d2 数组区间端点的坐标计算。

破题与推导： 设原串长度为 $n$。要在末尾补最少的字符，等价于在原串中找到一个最长的回文后缀。 假设原串的最长回文后缀是 $S[L \dots n-1]$，那么前缀 $S[0 \dots L-1]$ 就是多余出来的、破坏了整体对称性的部分。我们只需要把这段多余的前缀逆序翻转一下，像镜像一样拼接在原串的最末尾，就能用最少的代价补成全串回文。

• 结论：添加的最少字符数 = 多余前缀的长度 = $L$ = 总长度 $n$ - 最长回文后缀长度。

如何用 Manacher 判定回文后缀（或前缀）？ 回文后缀的本质，就是这个回文区间的右端点必须刚好顶到原串的最后一个字符（即坐标 $n-1$）。 我们利用算好的半径数组，遍历所有的中心 $i$：

1. 奇数回文：半径为 k = d1[i]，它的右端点落在 $i + k - 1$。
   • 若 $i + k - 1 == n - 1$，它就是一个回文后缀，长度为 $2k - 1$。
2. 偶数回文：半径为 k = d2[i]，它的右端点同样落在 $i + k - 1$。
   • 若 $i + k - 1 == n - 1$，它也是一个回文后缀，长度为 $2k$。

同理延伸：如果是要求解“最长回文前缀”或“在头部最少补字符”，只需要检查回文的左端点是否刚好顶到下标 0 即可。奇数左端点为 $i - k + 1 == 0$，偶数左端点为 $i - k == 0$。

💡 【自拟实战：末尾补全回文】

• 输入格式：输入一行由小写英文字母组成的字符串 $S$。
• 输出格式：输出最少需要在末尾添加的字符数。
• 数据范围：$1 \le |S| \le 10^6$。
• 样例输入：abac
• 样例输出：3

代码实现细节：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;

string s;
int d1[N], d2[N];
int n;

void solve(){
	cin>>s;
	n=s.size();
	
	// 1. 跑奇数 Manacher
	int l=0, r=-1;
	for(int i=0;i<n;i++){
		int k=(i>r?1:min(d1[l+r-i],r-i+1));
		while(i-k>=0 && i+k<n && s[i-k]==s[i+k]) k++;
		d1[i]=k;
		if(i+k-1>r){ l=i-k+1; r=i+k-1; }
	}
	
	// 2. 跑偶数 Manacher
	l=0, r=-1;
	for(int i=0;i<n;i++){
		int k=(i>r?0:min(d2[l+r-i+1],r-i+1));
		while(i-k-1>=0 && i+k<n && s[i-k-1]==s[i+k]) k++;
		d2[i]=k;
		if(i+k-1>r){ l=i-k; r=i+k-1; }
	}
	
	// 3. 寻找最长回文后缀
	int max_suffix_len = 1; // 至少最后一个字符本身是回文后缀
	
	for(int i=0;i<n;i++){
		// 检查奇数回文是否是后缀
		if(i + d1[i] - 1 == n - 1){
			max_suffix_len = max(max_suffix_len, 2 * d1[i] - 1);
		}
		// 检查偶数回文是否是后缀
		if(i + d2[i] - 1 == n - 1){
			max_suffix_len = max(max_suffix_len, 2 * d2[i]);
		}
	}
	
	// 最少添加字符数 = 总长度 - 最长回文后缀长度
	cout << n - max_suffix_len << '\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

手推验证样例（abac）：

• 对于奇数中心 $i=2$（字符 a），d1[2] = 1。右端点为 $2 + 1 - 1 = 2 \neq 3$，不是后缀。
• 对于奇数中心 $i=3$（字符 c），d1[3] = 1。右端点为 $3 + 1 - 1 = 3 == 3$，刚好触底！这是一个长度为 $2 \times 1 - 1 = 1$ 的回文后缀。
• 偶数中心均无法配对形成更长的后缀。 所以 max_suffix_len = 1。 我们需要补齐的字符数为 $4 - 1 = 3$（即将前缀 aba 逆序翻转后拼在最后，最终串变为 abacaba）。

九、考场避坑指南与教练提点

1. 手造极端小样自检： 写完代码后，绝对不要直接拿千行长串盲测。立刻在纸上自测这 4 个微型测试串：

   • "a"：单字符奇半径必为 1，偶半径全为 0，最长回文长度为 1；
   • "aa"：检验偶数中心是否生效，$d2[1]=1$，最长回文长度为 2；
   • "ab"：相邻不同字符，奇半径均为 1，偶半径全为 0，最长回文长度为 1；
   • "abba"：检验偶数中心扩展多层，$d2[2]=2$，最长回文长度为 4。

2. 偶数镜像的 +1 严防漏写： 再提醒一次：奇数镜像是 l + r - i，偶数镜像是 l + r - i + 1！漏了加 1，镜子就照偏了，不仅答案算错，还可能引发越界访问。

3. 1-based 与 0-based 的协调转换： 本讲采用 0-based，是为了让原串下标和 $c = L + \text{len} / 2$ 的中心公式直接对应。如果题目输入是 1-based，在读入询问后做一步 L--, R-- 即可接入。补空格的 1-based 写法也可以用，但半径和区间公式要一起保持一致，不要混用两套下标。

4. 回文子串计数：半径求和及 long long 累加见第七节；这是按出现位置计数，不能直接用来求本质不同的回文串数。