题目理解

题目要求找到最长的前缀和后缀，使得：

1. 前缀与后缀循环等价（即可以通过循环移位得到彼此）
2. 前缀与后缀长度相同，且总长度 ≤ n/2（不相交）
3. 在满足条件下长度最大

代码思路解析

1. 双哈希预处理

h1[i] = (h1[i - 1] * P % mod1 + a[i] - 'a' + 1) % mod1;
p1[i] = p1[i - 1] * P % mod1;

使用双哈希（模数 1e9+7 和 1e9+9）来支持 O(1) 的子串比较。

2. 函数 c(x, y, l, r)

比较子串 a[x..y] 和 a[l..r] 是否相等，使用双哈希验证。

3. 核心 DP 数组 f[i]

f[i] 表示：从位置 i+1 开始的最长子串长度，使得该子串等于从 n-i-f[i] 开始的后缀子串。

递推过程：

for (int i = n / 2 - 1; i >= 0; i--) {
    f[i] = f[i + 1] + 2;  // 继承并扩展
    while (f[i] && i + f[i] > n / 2) f[i]--;  // 保证不相交
    while (f[i] && !c(i + 1, i + f[i], n + 1 - i - f[i], n - i)) 
        f[i]--;  // 检查循环等价性
}

这里 f[i] 从后往前计算，利用 f[i+1] 的结果加速。

4. 最终答案计算

for (int i = 0; i <= n / 2; i++)
    if (c(1, i, n - i + 1, n))  // 前缀[1..i] == 后缀[n-i+1..n]
        res = max(res, i + f[i]);

对于每个可能的前后缀长度 i，如果前缀等于后缀，就尝试加上 f[i]（中间匹配的部分）。

样例演示

输入：

15
ababbabababbaab

过程：

• 计算哈希表
• 从后往前计算 f[i]
• 检查每个 i 是否满足前缀=后缀，并加上 f[i]
• 找到最大长度 6

复杂度分析

• 哈希预处理：O(n)
• f[i] 计算：均摊 O(n)（每个字符最多被检查两次）
• 总复杂度：O(n)

这个解法巧妙地利用哈希和动态规划，在 O(n) 时间内解决了问题。