CF700E Cool Slogans 后缀自动机 + right集合线段树合并 + 树形DP

怼烎@ 2021-11-17 16:16 205阅读 0赞

### 题目描述 ###

给出一个长度为n的字符串s\[1\]，由小写字母组成。定义一个字符串序列s\[1....k\],满足性质：s\[i\]在s\[i-1\] (i>=2)中出现至少两次（位置可重叠），问最大的k是多少，使得从s\[1\]开始到s\[k\]都满足这样一个性质。

发现 $s\[1...k\]$ 之间一定是互为后缀关系. 那么就可以建出后缀树，令 $dp\_\{u\}$ 表示 $u$ 节点代表子串的答案

维护 $top\_\{u\}$ 表示 $u$ 以及 $u$ 在后缀树的祖先中合法的且答案最大（答案相同则最短）的节点编号

$dp\_\{u\}\\Rightarrow dp\_\{top\_\{fa\}\}+1$ ，$fa$ 在 $u$ 中出现大于等于2次

$dp\_\{u\}=1,top\_\{u\}=top\_\{fa\}$，$fa$ 在 $u$ 中仅出现 $1$ 次

#include<bits/stdc++.h>
    #define maxn 400002 
    #define setIO(s) freopen(s".in","r",stdin) 
    using namespace std;   
    namespace tr 
    {
        #define lson t[x].l 
        #define rson t[x].r 
        #define mid ((l+r)>>1) 
        int cnt; 
        struct Node { int l,r; }t[maxn*20]; 
        void modify(int &x,int l,int r,int k)
        {
            if(!x) x=++cnt; 
            if(l==r) return; 
            if(k<=mid) modify(lson,l,mid,k); 
            else modify(rson,mid+1,r,k); 
        }
        int merge(int u,int v) 
        {
            if(!u||!v) return u+v; 
            int x=++cnt; 
            lson=merge(t[u].l,t[v].l); 
            rson=merge(t[u].r,t[v].r);    
            return x;             
        }
        int query(int x,int l,int r,int L,int R)
        {
            if(!x) return 0; 
            if(l>=L&&r<=R) return 1; 
            int tmp=0; 
            if(L<=mid) tmp+=query(lson,l,mid,L,R); 
            if(R>mid) tmp+=query(rson,mid+1,r,L,R); 
            return tmp; 
        }
    }; 
    namespace SAM 
    { 
        char str[maxn]; 
        int last,tot,n;  
        int trans[maxn][27],f[maxn],len[maxn],C[maxn],rk[maxn],top[maxn],dp[maxn],pos[maxn],rt[maxn];  
        void init() { last=tot=1; }
        void extend(int c,int i) 
        {  
            int np=++tot,p=last; 
            len[np]=len[p]+1,last=np; 
            while(p&&!trans[p][c]) trans[p][c]=np,p=f[p]; 
            if(!p) f[np]=1; 
            else 
            {
                int q=trans[p][c]; 
                if(len[q]==len[p]+1) f[np]=q; 
                else 
                {
                    int nq=++tot; 
                    len[nq]=len[p]+1; 
                    pos[nq]=pos[q];  
                    memcpy(trans[nq],trans[q],sizeof(trans[q])); 
                    f[nq]=f[q], f[np]=f[q]=nq; 
                    while(p&&trans[p][c]==q) trans[p][c]=nq,p=f[p]; 
                }
            }
            pos[np]=i; 
            tr::modify(rt[last],1,n,i);   
        }
        void prepare() 
        {
            int i,j; 
            init(); 
            scanf("%d%s",&n,str+1);  
            for(i=1;i<=n;++i) extend(str[i]-'a',i);  
            for(i=1;i<=tot;++i) ++C[len[i]]; 
            for(i=1;i<=tot;++i) C[i]+=C[i-1]; 
            for(i=1;i<=tot;++i) rk[C[len[i]]--]=i;    
            for(i=tot;i>1;--i) 
            {
                int u=rk[i]; 
                rt[f[u]]=tr::merge(rt[f[u]],rt[u]);  
            }                     
        }
        void calc() 
        {
            int i,j,ans=1; 
            for(i=2;i<=tot;++i) 
            {
                int u=rk[i],ff=f[rk[i]];  
                if(ff==1) { top[u]=u,dp[u]=1; continue; }  
                if(tr::query(rt[top[ff]],1,n,pos[u]-len[u]+len[top[ff]],pos[u]-1))
                    top[u]=u,dp[u]=dp[top[ff]]+1; 
                else 
                    top[u]=top[ff];       
                ans=max(ans,dp[u]);                 
            }
            printf("%d\n",ans);  
        }
    }; 
    int main()
    {
        //msetIO("input"); 
        SAM::prepare();                  
        SAM::calc(); 
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11141107.html