题解：洛谷 P8368（[LNOI2022] 串）

1. Description

给定一个字符串 S,要求求出一个字符串序列 \(\{T_i\}\)，满足 \(T_0\) 是 S 的子串，且对于 \(i\ne 0\)，\(|T_i|=|T_{i-1}|+1\)，且 \(S\) 存在一个子串 \(S^\prime\) 满足 \(S^\prime\) 长度为 \(|T_{i-1}|\) 的前缀为 \(T_{i-1}\)，长度为 \(|T_i|\) 的后缀为 \(T_{i-1}\)，求合法序列的最长长度。

2. Solution

感觉是一道不算很难的黑，难度有虚高嫌疑（？）。
一个结论是最优的序列一定是以空串开头的，这结论很显然，不过多赘述。
首先我们对限制条件进行一定的分析，方便我们写题。对于 \(T_i\) 和 \(T_{i-1}\)，因为 \(S^\prime\) 的长度为 \(|T_i|+1\)，所以长度为 \(|T_{i-1}|\) 的前缀和长度为 \(|T_i|\) 的后缀将共用 \([2,|T_{i-1}|]\) 的部分。
由此，我们可以想到倒着构造，对于 \(T_i=S[l,r]\)，\(T_{i-1}=S[l-1,r-2]\) 必然是一个合法的构造，此时 \(S^\prime=S[l-1,r]\)。
那么答案的下限就是 \(\lfloor\frac{n}{2}\rfloor\)，当初始的 \(r=n,l=\lfloor\frac{n}{2}\rfloor\) 时取到。
然后我们就需要考虑怎么增加这个答案，应该不难想到考虑一个子串在 \(S\) 中重复出现的情况，此时我们可以增加答案。
如何构造？我们假设 \(S[l_1,r_1]=S[l_2,r_2]\ (l_1<l_2)\)，如果 \(r_1\) 和 \(n\) 奇偶性相同，那么从 \([l_1+\frac{n-r_1}{2},n]\) 开始，一直平移，显然可以到达 \([l_1,r_1]\)，此时将这个区间视作 \([l_2,r_2]\)，继续进行平移，如此重复，每一次左端点平移到 \(l_1\)，就跳回到 \(l_2\)，直到区间长度为 \(0\) 为止，如果 \(r_i\) 和 \(n\) 奇偶性不同，那么从 \([l_1+\frac{n-r_1-1}{2},n-1]\) 开始即可。
这样答案就是 \(\frac{n-r_1}{2}+r_1-l_1+1\)，略微变换则有 \(\frac{n+r_1-l_1-l1+2}{2}\)，也就是 \(\frac{n+len-l_1}{2}\)。
考虑使用后缀数组求解，这个式子的最值必然由两个排名上相邻的后缀取得，理由是，如果 \(S[l_1,n],S[l_2,n]\) 在排名上不相邻，那么必然存在一个与 \(S[l_1,n]\) 在排名上相邻的后缀 \(S[x,n]\)，使得 \(\operatorname{LCP}(S[l_1,n],S[l_2,n])\le \operatorname{LCP}(S[l_1,n],S[x,n]),\min(x,l_1)\le l_1\)，得到的值显然更大。
那么代码的实现也就很简单了。

3. Code

/*by ChenMuJiu*/
/*略去缺省源与快读快写*/
const int N=5e5+5;
int n,ans;
int sa[N],rk[N],tmpsa[N],tmprk[N],cnt[N],f[N];
char s[N]; 
void init(int n){for(int i=1;i<=128;i++)cnt[i]=0;for(int i=1;i<=n;i++)cnt[s[i]]++;for(int i=1;i<=128;i++)cnt[i]+=cnt[i-1];for(int i=1;i<=n;i++)sa[cnt[s[i]]--]=i;for(int i=1,p=0;i<=n;i++){if(s[sa[i]]!=s[sa[i-1]])p++;rk[sa[i]]=p;}for(int k=1,now;k<n;k<<=1){now=0;for(int i=n-k+1;i<=n;i++)tmpsa[++now]=i;for(int i=1;i<=n;i++)cnt[i]=0;for(int i=1;i<=n;i++){cnt[rk[i]]++;if(sa[i]>k)tmpsa[++now]=sa[i]-k;}for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--)sa[cnt[rk[tmpsa[i]]]--]=tmpsa[i];for(int i=1;i<=n;i++)tmprk[i]=rk[i];for(int i=1,p=0;i<=n;i++){if(tmprk[sa[i]]==tmprk[sa[i-1]]&&tmprk[sa[i]+k]==tmprk[sa[i-1]+k])rk[sa[i]]=p;else rk[sa[i]]=++p;}}s[n+1]='#';for(int i=1,k=0,pos;i<=n;i++){if(rk[i]==1)continue;if(k)k--;pos=sa[rk[i]-1];while(s[i+k]==s[pos+k])k++;f[rk[i]]=k;}
}
signed main(){int t;read(t);while(t--){scanf("%s",s+1);n=strlen(s+1);init(n);ans=n/2;for(int i=2,len,l;i<=n;i++){len=f[i],l=min(sa[i-1],sa[i]);tomax(ans,(n+len-l+1)/2);}write(ans),Nxt;}
}