CF700E Cool Slogans

· · 题解

传送门

首先，我们可以强制 s_{i-1} 是 s_i 的后缀，这样是不会使答案变劣的，因为把 s_{i} 后面不能和 s_{i-1} 匹配的那段砍掉并不会影响答案。

所以我们选的 s 其实是后缀自动机 Parent Tree 上的一条从根出发的链部分节点，且同个节点最多选一个（因为同个节点的不同串不可能满足出现 2 次的关系）。但是现在问题来了，我们怎么知道这个节点中应该选哪个，所以这里先要知道一个引理：

对于节点 u 和节点 v 满足 u 是 v 的祖先，若取出 v 中最长的串，则 u 中所有的串在此串中出现的位置是一样的。

神 iostream 给出了严谨的证明，所以我这里给出一个可能会形象具体的，方便大家感性理解。

如图，线段代表的是 v 中的那个最长串的出现位置，点代表 u 中的串的出现位置，发现上面的结论不成立只有一种情况，即 u 中某个较短的串塞的进线段里，较长的串塞不进去，就是如下情况：

蓝线代表那个较长的串，红线代表较短的，但是可以发现每一个线段前面都有一小段一样的蓝的，把那一小段蓝的加进线段里也会形成一个和 v 的 endpos 相同的串，而且这个串比 v 中最长串，也就是图中的那个线段要长，因为 endpos 一样，这个新串也应该在 v 中，又因为它更长，这与图中线段是 v 中最长的串矛盾，所以结论成立。

我们选的那条链，深度最大的那个节点肯定贪心的选最长的，而深度第二大的因为深度最大的选了最长，根据引理，它选什么长度要么都可以要么都不行，所以它也应该贪心地选最长的......所以对于所有选的节点，我们都应该选最长。

接下来就可以直接 DP 了，f_u 表示从根一直下来选到 u，且 u 选了的最大答案，转移很显然是 f(u)=\max\{f(fa_u),f(v)+1\} ，其中 v 是 u 的祖先且在 u 中至少出现两次，考虑一个简单的优化：f 显然是关于深度单调不减的，所以不可能有 f(v) 能超过 f(fa_u)，其实我们只用管 f(v)=f(fa_u) 的 v 就好了，且这样的 v 肯定是希望它越浅越好，乱搞一下维护出这样的 v。

至于判断是否出现了 2 遍，套路的线段树合并维护 endpos 即可。 

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define N 400005
using namespace std;
inline int read(){
    int x=0,f=0; char ch=getchar();
    while(!isdigit(ch)) f|=(ch==45),ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
struct edge{
    int b,n;
}e[2*N];
int n,h[2*N],tot;
char s[N];
inline void charu(int a,int b){
    e[++tot].b=b,e[tot].n=h[a],h[a]=tot;
}
struct SuffixAutoMaton{
    int tail,pool,pos[2*N],nxt[2*N][26],fail[2*N],len[2*N];
    inline void init(){tail=pool=1,fail[1]=0;}
    inline void insert(int c){
        len[++pool]=len[tail]+1,pos[pool]=len[pool];
        int p=tail;tail=pool;
        for(;p && !nxt[p][c];p=fail[p]) nxt[p][c]=tail;
        if(!p) return (void)(fail[tail]=1);
        int q=nxt[p][c];
        if(len[p]+1==len[q]) return (void)(fail[tail]=q);
        len[++pool]=len[p]+1,fail[pool]=fail[q],pos[pool]=pos[q];
        memcpy(nxt[pool],nxt[q],sizeof(nxt[q]));
        fail[q]=fail[tail]=pool;
        for(;nxt[p][c]==q;p=fail[p]) nxt[p][c]=pool;
    }
}sam;
struct segmentTree{
    int ls,rs,sum;
}d[50*N];
int nd,rt[N*2];
void update(int &k,int l,int r,int x){
    k=++nd;
    if(l==r) return (void)(d[k].sum=1);
    int mid=l+r>>1;
    if(x<=mid) update(d[k].ls,l,mid,x);
    else update(d[k].rs,mid+1,r,x);
    d[k].sum=d[d[k].ls].sum+d[d[k].rs].sum;
}
int merge(int x,int y){
    if(!x || !y) return x|y;
    int k=++nd;
    d[k].sum=d[x].sum+d[y].sum;
    d[k].ls=merge(d[x].ls,d[y].ls);
    d[k].rs=merge(d[x].rs,d[y].rs);
    return k;
}
int query(int k,int l,int r,int x,int y){
    if(x<=l && r<=y) return d[k].sum;
    int mid=l+r>>1,res=0;
    if(x<=mid) res=query(d[k].ls,l,mid,x,y);
    if(mid+1<=y) res+=query(d[k].rs,mid+1,r,x,y);
    return res;
}
void dfs(int u){
    if(sam.pos[u]) update(rt[u],1,n,sam.pos[u]);
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].b;
        dfs(v);
        rt[u]=merge(rt[u],rt[v]);
    }
}
int f[2*N],ans,lnk[2*N];
void solve(int u,int fa){
    if(u!=1){
        int p=lnk[fa];f[u]=f[p];
        if(p==1) f[u]++;
        else if(query(rt[p],1,n,sam.pos[u]-sam.len[u]+sam.len[p],sam.pos[u]-1)) f[u]++;
    }
    lnk[u]=(f[u]==f[fa]?lnk[fa]:u);
    lnk[1]=1;
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].b;
        solve(v,u);
    }
    ans=max(ans,f[u]);
}
int main(){
    n=read();
    scanf("%s",s+1);
    sam.init();
    for(int i=1;i<=n;++i) sam.insert(s[i]-'a');
    for(int i=1;i<=sam.pool;++i) charu(sam.fail[i],i);
    dfs(1);
    solve(1,0);
    cout<<ans;
    return 0;
}