题目概述

给定一个字符串 $S$ ，要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i \in$ $[2, n]$ ，都有 $s_{i-1}$ 在 $s_i$ 中出现了至少 2 次 (可以有重叠部分，只要起始、结尾位置不同即可) 。

求可能的最大的 $k$ 的值（即序列的最大可能长度）。

解题报告

2022.11.25UPD：以前题解写的太抽象了，重新学了一遍。

超级结论题，直接上结论：

对于后缀自动机上的两个节点 $x,y$ ，如果 $x$ 是 $y$ 的祖先，那么对于 $x$ 节点中的任意一个子串，在 $y$ 的最长子串中，出现的位置以及次数均完全一致。

证明：如果不一致，假设 $x$ 节点中 $A$ 和 $B$ 在 $y$ 最长子串中出现位置不一致且 $A$ 比 $B$ 短，则存在一个子串 $Z$ ，$Z$ 是 $y$ 往前添加了若干个字符（使得 $y$ 恰好包含了 $B$ ），并且 $Z$ 不是 $y$ 节点中的子串。则 $Z$ 所在节点 $z$ 的 $Right$ 一定比 $y$ 节点的 $Right$ 小，也就是说，$B$ 的 $Right$ 也比 $A$ 的 $Right$ 小，与后缀自动机定义矛盾。因此得证。

因此，我们在后缀自动机 $Parent$ 树上从上往下考虑贪心，对于 $x$ 节点，一定是找最近的（即最短的）$y$ 子树节点，如果 $x$ 在 $y$ 中出现两次，就可以转移过去，否则不如直接继承 $x$ 。定义 $f_i$ 表示从根到 $i$ 节点的次数，以及 $pos_i$ 表示上一次的 $x$ 。再根据结论，对于每个节点只需要管最长的那个串就行了（因为短的出现位置也一样）。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400000,maxi=26,maxt=1e7;

int n,ha[maxn+5],who[maxn+5],ro[maxn+5],len,ls[maxt+5],rs[maxt+5],ans;char s[maxn+5];
int si=1,p=1,son[maxn+5][maxi],fa[maxn+5],MAX[maxn+5],ID[maxn+5],f[maxn+5],pos[maxn+5];

inline void Extend(int w,int i){
    int np=++si;MAX[np]=MAX[p]+1;ID[np]=i;while (p&&!son[p][w]) son[p][w]=np,p=fa[p];
    if (!p) fa[np]=1; else{
        int q=son[p][w];if (MAX[p]+1==MAX[q]) fa[np]=q; else{
            int nq=++si;MAX[nq]=MAX[p]+1;ID[nq]=i;memcpy(son[nq],son[q],sizeof(son[q]));
            fa[nq]=fa[q];fa[np]=fa[q]=nq;while (p&&son[p][w]==q) son[p][w]=nq,p=fa[p];
        }
    }p=np;
}
void Insert(int &p,int pos,int l=1,int r=n){
    if (!p) p=++len;if (l==r) return;int mid=l+(r-l>>1);
    if (pos<=mid) Insert(ls[p],pos,l,mid); else Insert(rs[p],pos,mid+1,r);
}
int Merge(int A,int B) {if (!A||!B) return A+B;int p=++len;ls[p]=Merge(ls[A],ls[B]);rs[p]=Merge(rs[A],rs[B]);return p;}
inline void Make(){
    for (int i=1;i<=si;i++) ha[MAX[i]]++;for (int i=1;i<=n;i++) ha[i]+=ha[i-1];for (int i=1;i<=si;i++) who[ha[MAX[i]]--]=i;
    for (int j=si,i=who[j];j>1;i=who[--j]) Insert(ro[i],ID[i]),ro[fa[i]]=Merge(ro[fa[i]],ro[i]);
}
bool Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return false;if (L==l&&r==R) return true;int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid);if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    return Ask(ls[p],L,mid,l,mid)||Ask(rs[p],mid+1,R,mid+1,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%s",&n,s+1);for (int i=1;i<=n;i++) Extend(s[i]-'a',i);Make();
    for (int j=(f[1]=0,pos[1]=ans=1,2),i=who[j];j<=si;i=who[++j]){
        if (fa[i]==1||Ask(ro[pos[fa[i]]],ID[i]-MAX[i]+MAX[pos[fa[i]]],ID[i]-1)) f[i]=f[fa[i]]+1,pos[i]=i;
        else f[i]=f[fa[i]],pos[i]=pos[fa[i]];ans=max(ans,f[i]);
    }printf("%d\n",ans);return 0;
}