[十二省联考2019]字符串问题——后缀自动机+parent树优化建图+拓扑序DP+倍增

爱被打了一巴掌 2022-01-13 04:19 169阅读 0赞

# 题目链接： #

[\[十二省联考2019\]字符串问题][2019]

首先考虑最暴力的做法就是对于每个$B$串存一下它是哪些$A$串的前缀，然后按每组支配关系连边，做一遍拓扑序DP即可。

但即使忽略判断前缀的时间，光是连边的时间就会爆炸，显然不能暴力连边。

对于前缀不好解决，可以将字符串翻转然后变成判断是否是后缀。

可以发现对于后缀自动机的$parent$树，每个节点是子树内所有节点的后缀。

那么我们可以利用$parent$树来优化建图过程，将树上每个点向子节点连边。

对于每个$A$串和$B$串在后缀自动机上匹配出对应节点，如果是$A$串就新建节点并将$parent$树上的对应节点连向它，如果是$B$串就新建节点连向$parent$树上的对应节点。

对于$80\\%$的数据，因为保证$B$串比$A$串短，所以对于$parent$树上的一个节点既有出点又有入点是合法的($100\\%$的部分最后再说)。

但现在只解决了建图的问题，字符串在后缀自动机上匹配的时间复杂度依旧无法保证，如何找到每个$A,B$串对应的节点？

因为$\[l,r\]$的串一定是$\[1,r\]$的串的后缀，所以$\[l,r\]$的串在$parent$树上对应的节点一定是$\[1,r\]$的串对应节点的祖先，那么我们可以记录一下所有$\[1,r\]$的串在$parent$树上对应的节点，然后倍增往上跳来找到$\[l,r\]$对应的节点。

对于$100\\%$的数据，不保证$B$串比$A$串短，那么就可能存在一个$B$串比一个$A$串长，但这两个串在$parent$树上对应的节点相同。如果像上述方式连边的话，就会导致这个$B$串能转移到$A$串。

对于这种情况，我们将连在$parent$树上同一点的所有串存起来，按长度从小到大为第一关键字、先$B$串后$A$串为第二关键字排序，将$parent$树上每个点与父节点之间的边拆开，在这两点之间建一串点，分别与排完序的$A,B$串新建点相连，再将这一串点依次相连，这样有了上下制约关系就不会导致上述情况发生了。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int len[1200010];
    int pre[1200010];
    int tr[1200010][26];
    int fa[1200010][19];
    int num[200010];
    int val[1200010];
    int head[1200010];
    int to[1400010];
    int next[1400010];
    int cnt;
    int last;
    int T;
    int tot;
    char ch[200010];
    int na,nb;
    int n,m;
    int l,r;
    int x,y;
    int a[200010];
    int b[200010];
    int d[1200010];
    queue<int>q;
    int vis[1200010];
    ll f[1200010];
    int sum;
    struct lty
    {
        int len,num,opt;
        lty(){}
        lty(int LEN,int NUM,int OPT){len=LEN,num=NUM,opt=OPT;}
        bool operator <(lty a)const
        {
            return len==a.len?num>a.num:len<a.len;
        }
    };
    vector<lty>v[400010];
    inline void add(int x,int y)
    {
        next[++tot]=head[x];
        head[x]=tot;
        to[tot]=y;
        d[y]++;
    }
    inline void insert(int x,int id)
    {
        int p=last;
        int np=++cnt;
        memset(tr[np],0,sizeof(tr[np]));
        last=np;
        len[np]=len[p]+1;
        num[id]=np;
        for(;p&&!tr[p][x];p=pre[p])
        {
            tr[p][x]=np;
        }
        if(!p)
        {
            pre[np]=1;
        }
        else
        {
            int q=tr[p][x];
            if(len[q]==len[p]+1)
            {
                pre[np]=q;
            }
            else
            {
                int nq=++cnt;
                memset(tr[nq],0,sizeof(tr[nq]));
                len[nq]=len[p]+1;
                pre[nq]=pre[q];
                memcpy(tr[nq],tr[q],sizeof(tr[q]));
                pre[q]=pre[np]=nq;
                for(;p&&tr[p][x]==q;p=pre[p])
                {
                    tr[p][x]=nq;
                }
            }
        }
    }
    inline void build()
    {
        for(int i=2;i<=cnt;i++)
        {
            fa[i][0]=pre[i];
        }
        for(int j=1;j<=18;j++)
        {
            for(int i=2;i<=cnt;i++)
            {
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
    }
    inline int ST(int x,int dis)
    {
        for(int i=18;i>=0;i--)
        {
            if(len[fa[x][i]]>=dis)
            {
                x=fa[x][i];
            }
        }
        return x;
    }
    inline void clear()
    {
        for(int i=1;i<=sum;i++)
        {
            v[i].clear();
        }
    }
    inline void solve()
    {
        scanf("%s",ch+1);
        n=strlen(ch+1);
        for(int i=1;i<=n;i++)
        {
            insert(ch[n-i+1]-'a',i);
        }
        build();
        sum=cnt;
        scanf("%d",&na);
        for(int i=1;i<=na;i++)
        {
            scanf("%d%d",&l,&r);
            a[i]=++cnt;
            int p=ST(num[n-l+1],r-l+1);
            v[p].push_back(lty(r-l+1,a[i],0));
            val[a[i]]=r-l+1;
        }
        scanf("%d",&nb);
        for(int i=1;i<=nb;i++)
        {
            scanf("%d%d",&l,&r);
            b[i]=++cnt;
            int p=ST(num[n-l+1],r-l+1);
            v[p].push_back(lty(r-l+1,b[i],1));
        }
        for(int i=2;i<=sum;i++)
        {
            sort(v[i].begin(),v[i].end());
            int sz=v[i].size();
            int now=pre[i];
            for(int j=0;j<sz;j++)
            {
                cnt++;
                add(now,cnt);
                if(!v[i][j].opt)
                {
                    add(cnt,v[i][j].num);
                }
                else
                {
                    add(v[i][j].num,cnt);
                }
                now=cnt;
            }
            add(now,i);
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add(a[x],b[y]);
        }
        for(int i=1;i<=cnt;i++)
        {
            f[i]=val[i];
            if(!d[i])
            {
                q.push(i);
                vis[i]=1;
            }
        }
        while(!q.empty())
        {
            int now=q.front();
            q.pop();
            for(int i=head[now];i;i=next[i])
            {
                if(f[to[i]]<f[now]+val[to[i]])
                {
                    f[to[i]]=f[now]+val[to[i]];
                }
                d[to[i]]--;
                if(!d[to[i]])
                {
                    q.push(to[i]);
                    vis[to[i]]=1;
                }
            }
        }
        ll ans=0;
        for(int i=1;i<=cnt;i++)
        {
            if(!vis[i])
            {
                printf("-1\n");
                clear();
                return;
            }
            ans=max(ans,f[i]);
        }
        printf("%lld\n",ans);
        clear();
    }
    inline void init()
    {
        cnt=last=1,tot=0;
        memset(head,0,sizeof(head));
        memset(to,0,sizeof(to));
        memset(val,0,sizeof(val));
        memset(num,0,sizeof(num));
        memset(pre,0,sizeof(pre));
        memset(tr[1],0,sizeof(tr[1]));
        memset(next,0,sizeof(next));
        memset(len,0,sizeof(len));
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            init();
            solve();
        }
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10676956.html

[2019]: https://www.luogu.org/problemnew/show/P5284