容易想到这题就是求在掐掉原字符串的一个 border 之后，再求最大 border ，使得两个 border 长度之和最大。
如果暴力的话就是 \(O(n^2)\) 的但是常数比较小，可以如果没有捆绑的话可以水到很多分。
这里令 \(f_i\) 为掐掉前 \(i\) 个，后 \(i\) 个之后，最大的 border。
明显的 \(f_i\le f_{i+1}+2\) 。
这样可以递推地求出最大的 \(f_i\) ，将 \(f_i\) 从 \(f_{i+1}+2\) 依次尝试，看哪一个是合法的 \(f_i\) ，记录并转到下一个 \(i-1\)。
时间复杂度均摊下来是 \(O(n)\) 的，因为至多加 \(\frac{n}{2}\) 次 2。
代码比较简单：
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC target("avx", "sse2")
#pragma GCC optimize("unroll-loops")
#define ull unsigned long long
#define int long long
using namespace std;
const int N = 1E6 + 5, base2 = 2333, mod = 1e9 + 7;
int n, ans;
int pre2[N],pw2[N],f[N],dp[N];
char s[N];
inline int cal2(int l, int r) { return ((pre2[r] - pre2[l - 1] * pw2[r - l + 1] % mod) % mod + mod) % mod; }
signed main() {scanf("%lld", &n);scanf("%s", s + 1);pw2[0] = 1;for (int i = 1; i <= n; i++) pw2[i] = pw2[i - 1] * base2 % mod;for (int i = 1; i <= n; i++) pre2[i] = (pre2[i - 1] * base2 % mod + s[i]) % mod;f[0]=-1;for(int i=2,j=0;i<=n;i++){while(~j && s[i]!=s[j+1])j=f[j];f[i]=++j;//cout<<f[i]<<endl;}for(int i=n/2;i>=1;i--){dp[i]=dp[i+1]+2;while(dp[i]){if((dp[i]+i)*2>n) dp[i]--;else if(cal2(i+1,i+dp[i]) != cal2(n-i-dp[i]+1,n-i))dp[i]--;else break;}}for(int i=f[n];i;i=f[i]){//cout<<i<<endl;if(i*2<=n) ans=max(ans,dp[i]+i);}cout << ans << endl;return 0;
}