M_sea

洛谷5284 [十二省联考2019]字符串问题
LuoguLOJ分析后缀自动机+树上倍增+后缀树优化连边+拓扑排序。考虑这样的构图方式:所有 $A$ 类串向它所支...
扫描右侧二维码阅读全文
04
2019/06

洛谷5284 [十二省联考2019]字符串问题

Luogu

LOJ

分析

后缀自动机+树上倍增+后缀树优化连边+拓扑排序。

考虑这样的构图方式:所有 $A$ 类串向它所支配的 $B$ 类串连边,所有 $B$ 类串向以这个 $B$ 类串为前缀的 $A$ 类串连边,同时把所有 $A$ 类串的长度作为该点的点权,那么我们就等于要求最长路。

直接做是 $O(n^3)$ 的,考虑怎么优化这个东西。

对反串建后缀自动机,然后第二类边就等于每个节点向子树中所有节点连边。这个可以线段树优化连边但是没必要,事实上直接在 $\mathrm{parent}$ 树上从上往下连边即可。

具体怎么找某个串对应的节点,直接在 $\mathrm{parent}$ 树上连边倍增。

另外注意后缀自动机的一个节点可能存着很多串,所以要把这些存着的串按长度排序拉一条链出来,如果长度相同 $A$ 类串放后面。

然后直接拓扑排序求出最长路即可,有环就输出 $-1$ 。

另外:数据千万条,清空第一条。多测不清空,爆零两行泪。

实现起来细节比较多,详见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=800000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N],deg[N],e_cnt=0;

inline void addEdge(int u,int v) {
    e[++e_cnt]=(Edge){v,head[u]},head[u]=e_cnt;
    ++deg[v];
}

int n,na,nb,last,cnt,tot,sz;
int fa[N],len[N],ch[N][26];
int a[N],b[N];
int f[20][N],pos[N],mark[N],lst[N];
ll dis[N];
vector<int> vec[N];
char s[N];

inline void extend(int c) {
    int p=last,np=++cnt; last=np,len[np]=len[p]+1;
    for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if (!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if (len[p]+1==len[q]) fa[np]=q;
        else {
            int nq=++cnt; len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}

inline int find(int u,int l) {
    for (re int i=19;~i;--i)
        if (f[i][u]&&len[f[i][u]]>=l) u=f[i][u];
    return u;
}

inline int cmp(int x,int y) {
    return len[x]<len[y]||(len[x]==len[y]&&mark[x]<mark[y]);
}

int main() {
    int T=read();
    while (T--) {
        //建SAM
        scanf("%s",s+1),n=strlen(s+1),last=cnt=1;
        for (re int i=n;i;--i) extend(s[i]-'a'),pos[i]=last;
        for (re int i=1;i<=cnt;++i) f[0][i]=fa[i];
        for (re int i=1;i<=19;++i)
            for (re int j=1;j<=cnt;++j)
                f[i][j]=f[i-1][f[i-1][j]];

        //处理A、B串
        na=read(),sz=cnt;
        for (re int i=1;i<=na;++i) {
            ++sz;
            int l=read(),r=read(),x=find(pos[l],r-l+1);
            mark[sz]=1,len[sz]=r-l+1,vec[x].push_back(sz),a[i]=sz;
        }
        nb=read();
        for (re int i=1;i<=nb;++i) {
            ++sz;
            int l=read(),r=read(),x=find(pos[l],r-l+1);
            len[sz]=r-l+1,vec[x].push_back(sz),b[i]=sz;
        }

        //建图
        for (re int i=1;i<=cnt;++i)
            sort(vec[i].begin(),vec[i].end(),cmp);
        for (re int i=1;i<=cnt;++i) {
            int t=i;
            for (re int j:vec[i]) {
                addEdge(t,j);
                if (!mark[j]) t=j;
            }
            lst[i]=t;
        }
        for (re int i=2;i<=cnt;++i) addEdge(lst[fa[i]],i);
        for (re int i=1;i<=sz;++i)
            if (!mark[i]) len[i]=0;
        int m=read();
        for (re int i=1;i<=m;++i) {
            int x=read(),y=read();
            addEdge(a[x],b[y]);
        }
        
        //求最长路
        queue<int> Q; ll ans=0;
        for (re int i=1;i<=sz;++i)
            if (!deg[i]) Q.push(i);
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            ans=max(ans,dis[u]+len[u]);
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v;
                dis[v]=max(dis[v],dis[u]+len[u]);
                if (!--deg[v]) Q.push(v);
            }
        }
        int flag=0;
        for (re int i=1;i<=sz;++i)
            if (deg[i]) { flag=1; break; }
        if (flag) puts("-1");
        else printf("%lld\n",ans);

        //数据千万条,清空第一条。多测不清空,爆零两行泪。
        for (re int i=1;i<=cnt;++i) fa[i]=0,memset(ch[i],0,sizeof(ch[i]));
        for (re int i=1;i<=sz;++i)
            vec[i].clear(),mark[i]=len[i]=head[i]=dis[i]=deg[i]=0;
        e_cnt=tot=0;
    }
    return 0;
}
最后修改:2019 年 06 月 04 日 08 : 00 PM

2 条评论

  1. smy

    在,这题细节哪里有鱼多了qwq

    1. M_sea
      @smy

      你说的对

发表评论