首先感谢 高一零起点 $Au$ 的学长 对本蒟蒻的细心教导。$sto$ $wind$_$whisper$ $orz$

题目传送门

题意分析

给定一个英文小写字母构成的字符串 $S$，找到一个尽可能长的字符串序列$(T_0,T_1,\dots ,T_l)$，满足：

• $T_0$ 是 $S$ 的子串；
• $\forall 1\le i\le l$，$\mid T_i\mid -\mid T_{i-1}\mid =1$；
• $\forall 1\le i\le l$，存在 $S$ 的一个长度为 $\mid T_i\mid +1$ 的子串 $S_i^{\prime }$，使得 $S_i^{\prime }$ 的长度为 $\mid T_{i-1}\mid$ 的前缀为 $T_{i-1}$，长度为 $\mid T_i\mid$ 的后缀为 $T_i$。

输出这样的字符串序列的长度最大值$($即 $l$ 的最大值$)$。

算法分析

俗话说，正难则反。我们逆向来想如何构造可行的字符串。那么可以按如下方法构造：$[i,j]\to [i-1,j-2]\to [i-2,j-4]\to \dots$ 一直这样下去，直到长度为 $0$ 或者到头了。那么答案有一个最小值是 $\lfloor n/2\rfloor$。

用下面的图能很好的说明为什么这么构造是合法的。

由于题目中说一个是前缀，一个是后缀，那么这么构造就行。接下来的 $T_{i-2}$ 与这种构造方法相同。

解决完合法性，我们考虑如何统计答案。上文中说到，答案有一个下界是 $\lfloor n/2\rfloor$，这种情况是一直往前跳，跳到空串为止。那么有没有情况是可以更新这个答案的呢？有！看下面这张图。

字符串 $T_{i-1}$ 在大串 $S$ 中出现了两次，那么我们在从 $T_i$ 跳到 $T_{i-1}$ 的时候，可以跳到后面那个 $T_{i-1}$，这样的话当跳到前面那个 $T_{i-1}$ 的时候，我们就可以跳回到后面的 $T_{i-1}$。那么对于出现次数 $\ge 2$ 的串 $[l,r]$，选择从它开始跳，答案为 $r-l+1+\lfloor (n-r)/2\rfloor$。我们求出以每个下标为右端点的最长的出现次数 $\ge 2$的串，取个 $\max$，然后再和答案下界 $\lfloor n/2\rfloor$ 取个 $\max$ 即可。

总代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
inline void print(int x){if(x < 0) putchar('-'),x = -x;if(x >= 10) print(x / 10);putchar(x % 10 + '0');
}
const int M = 1e6+100;
int ch[M][26],len[M],fa[M],head[M],siz[M],pos[M];
char s[M];
int T,n,cnt,ans,tot=1,np=1;
struct edge{int to,nxt;
}e[M];
inline void add(int u,int v){e[++cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt;
}
inline void init(){rep(i,1,tot){memset(ch[i],0,sizeof(ch[i]));head[i] = 0;siz[i] = 0;}cnt = ans = 0;tot = np = 1;
}
inline void sam_extend(int c,int id){int p = np; np = ++tot;len[np] = len[p] + 1;siz[np] = 1;pos[np] = id;for( ; p && !ch[p][c] ; p = fa[p]) ch[p][c] = np;if(p == 0) fa[np] = 1;else{int q = ch[p][c];if(len[q] == len[p] + 1) fa[np] = q;else{int nq = ++tot;fa[nq] = fa[q]; fa[q] = nq; fa[np] = nq;len[nq] = len[p] + 1;pos[nq] = n+1;siz[nq] = 0;for( ; p && ch[p][c]==q ; p = fa[p]) ch[p][c] = nq;memcpy(ch[nq],ch[q],sizeof(ch[nq]));}}
}
inline void dfs(int u){for(re int i(head[u]) ; i ; i=e[i].nxt){int v = e[i].to;dfs(v);siz[u] += siz[v];pos[u] = min(pos[u],pos[v]);}if(siz[u] > 1) ans = max(ans,len[u]+(n-pos[u])/2);
}
inline void work(){init();scanf("%s",s+1);n = strlen(s+1);rep(i,1,n) sam_extend(s[i]-'a',i);rep(i,2,tot) add(fa[i],i);ans = n/2;dfs(1);printf("%d\n",ans);
}
signed main(){T = read();while(T--) work();return 0;
}