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

佚名 6年前 (2019-04-08) 随笔 1545人围观抢沙发百度已收录

题目

其实是一道熟练的套路题啊

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

之后我由于树上倍增没加\(1\)而熟练保龄

首先\(SA\)做这道题是肯定可以的，我们二分+\(St\)表就可以求出每一个\(B\)串的扩展区间(就是这个区间内的后缀和这个串的\(lcp\)都大于等于这个串的长度)，之后直接主席树优化建图就好了

之后就会收获\(TLE\)的好成绩

显然我们并不需要那么麻烦，我们发现\(SAM\)的\(parent\)是一个天然的树形结构，可以直接用来帮助我们优化建图

于是我们可以直接在\(SAM\)上利用树上倍增直接定位好子串，对于每一个\(A\)串，向对应的\(B\)串连边就好了，边权就是\(A\)串的长度

之后一波码码码就会发现过不了第三个样例，调一调发现有一些子串定位在一起了

于是考虑我们舍弃后缀自动机的最小性，我们考虑对于每一个被定位了多次的位置拆出多个点来，毕竟\(SAM\)上一个节点代表的本来也就不是一个子串

之后按照上面的方式建图跑一波拓扑排序就够了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<set>
#define re register
#define mp std::make_pair
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=4e5+16;
typedef std::pair<int,int> pii;
std::set<pii> s;
inline int read() {
    char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,w;}e[maxn<<1];
int T,n,m,lst,cnt,num,K,tmp;
char S[maxn>>1];
int pos[maxn>>1];
int l[maxn],r[maxn],p[maxn],deep[maxn],lg[maxn>>1],g[maxn];
int len[maxn],son[maxn][26],fa[maxn],A[maxn],f[maxn][20],head[maxn<<1];
int c[maxn<<1],tax[maxn>>1],q[maxn<<1],a[maxn<<1];
std::vector<pii> d[maxn];
std::vector<int> v[maxn];
LL ans,dp[maxn<<1];
inline void add(int x,int y,int w) {
    e[++num].v=y;e[num].nxt=head[x];
    head[x]=num;c[y]++;e[num].w=w;
}
inline void ins(int c,int o) {
    int p=++cnt,f=lst;lst=p;
    len[p]=len[f]+1,pos[o]=p;
    while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
    if(!f) {fa[p]=1;return;}
    int x=son[f][c];
    if(len[x]==len[f]+1) {fa[p]=x;return;}
    int y=++cnt;
    len[y]=len[f]+1,fa[y]=fa[x],fa[p]=fa[x]=y;
    for(re int i=0;i<26;i++) son[y][i]=son[x][i];
    while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
inline void Pre(int L) {
    for(re int i=1;i<=cnt;i++) tax[len[i]]++;
    for(re int i=1;i<=L;i++) tax[i]+=tax[i-1];
    for(re int i=cnt;i;--i) A[tax[len[i]]--]=i;
    for(re int i=1;i<=cnt;i++) {
        int x=A[i];
        deep[x]=deep[fa[x]]+1;
        v[fa[x]].push_back(x);
    }
    for(re int i=1;i<=L;i++) tax[i]=0;
}
inline int jump(int x,int l) {
    for(re int j=lg[deep[x]];j>=0;--j) 
    if(len[f[x][j]]>=l) x=f[x][j];
    pii t=mp(x,l);
    if(s.find(t)==s.end()) g[x]++,s.insert(t);
    return x;
}
void dfs(int x,int fa) {
    if(fa) add(fa,x,0);
    int h=0;
    std::sort(d[x].begin(),d[x].end());
    if(d[x].size()) {
        p[d[x][0].second]=x;
        for(re int i=1;i<d[x].size();i++) {
            if(d[x][i].first!=d[x][i-1].first) {h=i;break;}
            p[d[x][i].second]=x;
        }
    }
    int pre=x;
    while(g[x]>1) {
        ++cnt;g[x]--;
        p[d[x][h].second]=cnt;
        for(re int i=h+1;i<d[x].size();i++) {
            if(d[x][i].first!=d[x][i-1].first) {h=i;break;}
            p[d[x][i].second]=cnt;
        }
        add(pre,cnt,0);pre=cnt;
    }
    for(re int i=0;i<v[x].size();i++) dfs(v[x][i],pre);
}
int main() {
    T=read();
    lg[1]=1;//倍增不加1，爆零两行泪。
    for(re int i=2;i<=200005;i++) lg[i]=lg[i>>1]+1;
    while(T--) {
        s.clear();
        for(re int i=1;i<=cnt;i++) deep[i]=head[i]=c[i]=a[i]=dp[i]=0;
        for(re int i=1;i<=tmp;i++) v[i].clear(),d[i].clear();
        for(re int i=1;i<=tmp;i++) memset(son[i],0,sizeof(son[i])),fa[i]=0,g[i]=0;
        num=0;lst=cnt=1;
        scanf("%s",S+1);int L=strlen(S+1);
        for(re int i=L;i;--i) ins(S[i]-'a',i);
        Pre(L);
        for(re int i=2;i<=cnt;i++) 
            f[i][0]=fa[i];
        for(re int j=1;j<=lg[L];j++)
            for(re int i=2;i<=cnt;i++) 
                f[i][j]=f[f[i][j-1]][j-1];
        n=read();
        for(re int i=1;i<=n;i++) 
            l[i]=read(),r[i]=read(),p[i]=jump(pos[l[i]],r[i]-l[i]+1);
        m=read();
        for(re int i=n+1;i<=n+m;i++) 
            l[i]=read(),r[i]=read(),p[i]=jump(pos[l[i]],r[i]-l[i]+1);
        for(re int i=1;i<=n+m;i++) 
            d[p[i]].push_back(mp(r[i]-l[i]+1,i));
        tmp=cnt;
        dfs(1,0);
        for(re int i=1;i<=n;i++) a[p[i]]=r[i]-l[i]+1;
        K=read();
        for(re int x,y,i=1;i<=K;i++) {
            x=read(),y=read();
            add(p[x],p[y+n],r[x]-l[x]+1);
        }
        int tot=0;ans=0;
        q[++tot]=1;
        for(re int i=1;i<=tot;i++) {
            int x=q[i];
            ans=max(ans,dp[x]+a[x]);
            for(re int j=head[x];j;j=e[j].nxt) {
                c[e[j].v]--;
                dp[e[j].v]=max(dp[e[j].v],dp[x]+e[j].w);
                if(!c[e[j].v]) q[++tot]=e[j].v;
            }
        } 
        if(tot<cnt) puts("-1");
        else printf("%lld\n",ans);
    }
    return 0;
}