显然答案下界为 \(\lfloor\frac{n}{2}\rfloor\)。采用一种对着题意模拟的策略：假设我们初始的区间为 \([l,r]\)，然后逐步向左平移，也就是：\([l,r],[l-1,r-2],[l-2,r-4],\dots\) 直到碰到边界（平移的次数 \(+1\) 就等于 \(m\)）。显然 \(l\) 取 \(\lfloor\frac{n}{2}\rfloor\)，\(r\) 取 \(n\) 时最优，也就是我们所说的答案下界。
之后考虑怎么尽量地延长这个平移的过程，不难发现：当我们平移到一个串，假设原串中后面还有出现过这个串，那么它就可以一直平移。直到到区间长度为 \(0\)。稍作推理易发现，假设我们的区间为 \([l,r]\)，那么最终经过当前区间的最大 \(m\) 为 \(r-l+1+\lfloor\frac{n-r}{2}\rfloor\)。
直接构建后缀数组，枚举左端点，然后贪心统计贡献就行了（观察式子，会发现左端点固定右端点大的较优）。
代码实现中的初始化要额外注意。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
const int N = 5e5 + 10;
struct SA{
int n, m, c[N], sa[N], rk[N], rk2[N], h[N];
char s[N];
void rsort(){
fill(c, c + m + 1, 0);
FL(i, 1, n) c[rk[i]]++;
FL(i, 1, m) c[i] += c[i - 1];
FR(i, n, 1) sa[c[rk[rk2[i]]]--] = rk2[i];
}
void ssort(){
FL(i, 1, n) rk[rk2[i] = i] = s[i];
m = 126, rsort();
for(int k = 1; k <= n && (k == 1 || m < n); k <<= 1){
int t = 0;
FL(i, n - k + 1, n) rk2[++t] = i;
FL(i, 1, n) if(sa[i] > k) rk2[++t] = sa[i] - k;
rsort(), copy(rk, rk + n + 1, rk2);
rk[sa[1]] = m = 1;
FL(i, 2, n){
if(rk2[sa[i]] != rk2[sa[i - 1]])
rk[sa[i]] = ++m;
else if(rk2[sa[i] + k] != rk2[sa[i - 1] + k])
rk[sa[i]] = ++m;
else rk[sa[i]] = m;
}
}
int k = 0; fill(h, h + n + 2, 0);
FL(i, 1, n) if(rk[i] > 1){
if(k) k--;
while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
h[rk[i]] = k;
}
}
void build(char str[]){
copy(str, str + strlen(str + 1) + 2, s);
n = strlen(s + 1), ssort();
}
} sa;
char s[N]; int ans;
void solve(){
scanf("%s", s + 1), sa.build(s), ans = sa.n / 2;
FL(i, 1, sa.n){
int l = max(sa.h[i + 1], sa.h[i]);
ans = max(ans, l + (sa.n - (sa.sa[i] + l - 1)) / 2);
}
printf("%d\n", ans);
}
int main(){
int T; scanf("%d", &T);
while(T--) solve();
}