String Journey
题面翻译
对于一个字符串数组 \(t_1, \ldots, t_k\)，若对于每一个 \(t_i\) 都是 \(t_{i-1}\) 的真子串的话，即 \(t_i\) 是 \(t_{i - 1}\) 的子串且 \(t_i \ne t_{i-1}\)，则称为有序串组，列如 \(\{\mathtt{ab}, \mathtt{b}\}\) 是，\(\{\mathtt{ab}, \mathtt{c}\}\) 和 \(\{ \mathtt{a}, \mathtt{a}\}\) 不是。
给定字符串 \(s\)，构造有序串组 \(t_1,\ldots,t_k\) 和任意字符串数组 \(u_1,\ldots,u_{k+1}\)，使 \(s=u_1+t_1+u_2+t_2 + \cdots +t_k+u_{k+1}\)，其中 \(+\) 为字符串的拼接
现在给定一个字符串，求满足条件的最大 \(k\)。
输入格式：
一个字符串 \(s\)
输出格式：
一个整数 \(k\)
题目描述
We call a sequence of strings $ t_{1},...,t_{k} $ a journey of length $ k $ , if for each $ i>1 $ $ t_{i} $ is a substring of $ t_{i-1} $ and length of $ t_{i} $ is strictly less than length of $ t_{i-1} $ . For example, $ {ab,b} $ is a journey, but $ {ab,c} $ and $ {a,a} $ are not.
Define a journey on string $ s $ as journey $ t_{1},...,t_{k} $ , such that all its parts can be nested inside $ s $ in such a way that there exists a sequence of strings $ u_{1},...,u_{k+1} $ (each of these strings can be empty) and $ s=u_{1}t_{1}u_{2}t_{2}...\ u_{k}t_{k}u_{k+1} $ . As an example, $ {ab,b} $ is a journey on string $ abb $ , but not on $ bab $ because the journey strings $ t_{i} $ should appear from the left to the right.
The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string $ s $ .
输入格式
The first line contains a single integer $ n $ ( $ 1<=n<=500000 $ ) — the length of string $ s $ .
The second line contains the string $ s $ itself, consisting of $ n $ lowercase Latin letters.
输出格式
Print one number — the maximum possible length of string journey on $ s $ .
样例 #1
样例输入 #1
7
abcdbcc
样例输出 #1
3
样例 #2
样例输入 #2
4
bbcb
样例输出 #2
2
提示
In the first sample, the string journey of maximum length is $ {abcd,bc,c} $ .
In the second sample, one of the suitable journeys is $ {bb,b} $ .
为了方便，把字符串倒过来，问题变成问一个最长的字符串序列，每个字符串是下一个字符串的子串。
一定存在一个最长的字符串序列满足 \(|t_i|=i\)，第 \(i\) 个串是上一个串前加或者后加字符。
定义 \(dp_i\) 为以 \(i\) 结尾的串，最长是多长（也就是前面有多少个），暴力哈希判断转移，我们有了 \(O(n^2)\) 的做法。
由于 \(dp_i\) 是 \(O(\sqrt{n})\) 的，转移时可以枚举长度，复杂度降到 \(O(\sqrt n)\)
考虑找一些性质，设 \(l_i\) 表示 \(i-dp_i+1\)，那么 \(l_i\) 具有单调性。
这是因为如果 \(l_{i-1}>l_i\)，那么 \(i-1\) 被 \(i\) 完全严格包含，不可能。
所以考虑双指针维护。现在要判断 \([l+1,r]\) 和 \([l,r-1]\) 中是否有一个是在 \(l\) 的前面存在过的。
对 SAM 每个节点记录 \(mx_i\)，表示该节点出现过的串中最长的是哪个，明显只有最长的有用。同时维护出 \([l+1,r]\) 和 \([l,r-1]\) 所在节点，判断一下即可。
\(l\) 往右移动的时候要把 \(l\) 为结尾的串加入 SAM 中，可以不断跳父亲改，直到父亲的最大长度为该节点的最大长度。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,ch[N][30],l[N],fa[N],ls=1,idx=1,r[N],mx[N],ans=1,p[N],g,h;
char s[N];
void ins(int s)
{
int u=ls,k=++idx;
ls=k;
l[k]=l[u]+1;
while(u&&!ch[u][s])
ch[u][s]=k,u=fa[u];
if(!u)
fa[k]=1;
else
{
int p=ch[u][s];
if(l[p]==l[u]+1)
fa[k]=p;
else
{
int v=++idx;
memcpy(ch[v],ch[p],sizeof(ch[0]));
l[v]=l[u]+1,fa[v]=fa[p];
fa[p]=fa[k]=v;
while(u&&ch[u][s]==p)
ch[u][s]=v,u=fa[u];
}
}
}
void add(int x)
{
if(l[x]==mx[x])
return;
mx[x]=l[x];
add(fa[x]) ;
}
int main()
{
scanf("%d%s",&n,s+1);
reverse(s+1,s+n+1);
for(int i=1;i<=n;i++)
ins(s[i]-'a');
p[1]=ch[1][s[1]-'a'];
r[1]=1;
for(int i=2;i<=n;i++)
{
p[i]=ch[p[i-1]][s[i]-'a'],r[i]=r[i-1];
g=p[i-1],h=p[i];
if(i-r[i]<=l[fa[h]])
h=fa[h];
while(mx[g]<i-r[i]&&mx[h]<i-r[i])
{
mx[p[r[i]]]=max(mx[p[r[i]]],r[i]-r[r[i]]+1);
add(fa[p[r[i]]]);
++r[i];
if(i-r[i]<=l[fa[g]])
g=fa[g];
if(i-r[i]<=l[fa[h]])
h=fa[h];
if(i-r[i]<l[fa[p[i]]])
p[i]=fa[p[i]];
}
ans=max(ans,i-r[i]+1);
}
printf("%d",ans);
}