字符串问题

字符串问题

题目背景
Yazid 和 Tiffany 喜欢字符串问题。在这里，我们将给你介绍一些关于字符串的基本概念。

对于一个字符串 $S$， 我们定义 $lvert S vert$ 表示 $S$ 的长度。

接着，我们定义该串的子串 $Sleft( {L,R} ight)$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串，特别地，如果 $L < 1$ 或 $R > lvert S vert$ 或 $L > R$，则 $Sleft( {L,R} ight)$ 表示空串。

我们说两个字符串相等，当且仅当它们的长度相等，且从左至右各位上的字符依次相同。

我们说一个字符串 $T$ 是 $S$ 的**前缀**，当且仅当 $Sleft( 1,lvert T vert ight)=T$。

两个字符串 $S,T$ 相加 $S+T$ 表示的是在 $S$ 后紧挨着写下 $T$ 得到的长度为 $lvert S vert+lvert T vert$ 的字符串。

题目描述
现有一个字符串 $S$。

Tiffany 将从中划出 $n_a$ 个子串作为 A 类串，第 $i$ 个（$1leq ileq n_a$）为 $A_i = Sleft( la_i, ra_i ight)$。

类似地，Yazid 将划出 $n_b$ 个子串作为 B 类串，第 $i$ 个（$1leq ileq n_b$）为 $B_i = Sleft( lb_i, rb_i ight)$。

现额外给定 $m$ 组支配关系，每组支配关系 $left( x,y ight)$ 描述了第 $x$ 个 A 类串**支配**第 $y$ 个 B 类串。

求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T=t_1 + t_2 +dots +t_k$（$kgeq 0$）满足：

- 分割中的每个串 $t_i$ 均为 A 类串：即存在一个与其相等的 A 类串，不妨假设其为 $t_i = A_{id_i}$。
- 对于分割中所有相邻的串 $t_i , t_{i+1}$（$1leq i < k$），都有存在一个 $A_{id_i}$ 支配的 B 类串，使得该 B 类串为 $t_{i+1}$ 的前缀。

方便起见，你只需要输出这个最大的长度即可。

特别地，如果存在无限长的目标串（即对于任意一个正整数 $n$，都存在一个满足限制的长度超过 $n$ 的串），请输出 $-1$。

---

solution

首先考虑暴力建图：A向支配的B连，B向前缀包含它的连。然后跑拓扑序dp。 40‘（我这咋只有20）

用sam优化:用反串建，则x为x的后代的前缀。

那么可以把par树连起来，然后支配边照常连，边数2n 。80’

不能满分是因为如果b[i]>a[i],连边后可能两个B被压在了同一个节点，但是一个可以被支配，一个不行。

把一个sam节点上的所有串按长度排序，从长度小的开始连，每次当前点与它的上一个b点。相当于串了起来。

这样子如果A能支配某一个B1，那么他只会连到这个B1，然后再间接的连到一个比B1长的B2...

而如果B2是某个串的前缀，那么B1也是。

于是就好了。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define maxn 800005
using namespace std;
int T,na,nb,m,cnt,rt,la,al;
int head[maxn],tot,pl[maxn],f[maxn][22],out[maxn],top[maxn];
long long dp[maxn];char ch[maxn];
vector<int>G[maxn],p[maxn];
struct node{int v,nex;}e[maxn*2];
struct no{
    int par,nex[26],Max,ed;
}s[maxn];
struct Node{
    int l,r,len;
}a[maxn],b[maxn];
void Q(){
    for(int i=0;i<=cnt+na+nb;i++){
        head[i]=pl[i]=0;
        out[i]=0;G[i].clear();p[i].clear();
        dp[i]=top[i]=0;
    }
    cnt=rt=la=1;tot=0;
    memset(f,0,sizeof f);
    memset(s,0,sizeof s);
}
void ins(int c,int id){
    int np=++cnt,p=la;la=np;
    s[np].ed=id;s[np].Max=s[p].Max+1;pl[id]=cnt;
    for(;p&&!s[p].nex[c];p=s[p].par)s[p].nex[c]=np;
    if(!p)s[np].par=rt;
    else {
        int q=s[p].nex[c];
        if(s[q].Max==s[p].Max+1)s[np].par=q;
        else {
            int nq=++cnt;
            s[nq].Max=s[p].Max+1;s[nq].par=s[q].par;
            for(int i=0;i<26;i++)s[nq].nex[i]=s[q].nex[i];
            s[q].par=s[np].par=nq;
            for(;s[p].nex[c]==q;p=s[p].par)s[p].nex[c]=nq;
        }
    }
}
void dfs(int k,int fa){
    f[k][0]=fa;
    for(int i=0;i<G[k].size();i++)dfs(G[k][i],k);
}
bool cmp(int A,int B){
    int xa=A,xb=B;
    if(A>cnt+na)A=b[A-cnt-na].len;
    else A=a[A-cnt].len;
    if(B>cnt+na)B=b[B-cnt-na].len;
    else B=a[B-cnt].len; 
    return A<B||A==B&&xa>xb;
}
void add(int t1,int t2){
    e[++tot].v=t1;e[tot].nex=head[t2];head[t2]=tot;
    out[t1]++;
}
void init(){
    scanf("%s",ch+1);int len=strlen(ch+1);
    for(int i=len;i>=1;i--){
        ins(ch[i]-'a',i);
    }
    scanf("%d",&na);for(int i=1;i<=na;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].len=a[i].r-a[i].l+1;
    scanf("%d",&nb);for(int i=1;i<=nb;i++)scanf("%d%d",&b[i].l,&b[i].r),b[i].len=b[i].r-b[i].l+1;
    for(int i=1;i<=cnt;i++)G[s[i].par].push_back(i);
    dfs(rt,0);
    for(int j=1;j<=20;j++)
    for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=na;i++){
        int t=pl[a[i].l],L=a[i].len;
        for(int j=20;j>=0;j--){
            int v=f[t][j];if(s[v].Max>=L)t=v;
        }
        p[t].push_back(cnt+i);
    }
    for(int i=1;i<=nb;i++){
        int t=pl[b[i].l],L=b[i].len;
        for(int j=20;j>=0;j--){
            int v=f[t][j];if(s[v].Max>=L)t=v;
        }
        p[t].push_back(cnt+na+i);
    }
    for(int i=1;i<=cnt;i++)sort(p[i].begin(),p[i].end(),cmp);
    
    for(int i=1;i<=cnt;i++){
        int lb=i;
        for(int j=0;j<p[i].size();j++){
            int t=p[i][j];
            if(t>cnt+na)add(lb,t),lb=t;
            else add(lb,t);
        }
        top[i]=lb;
    }
    for(int i=1;i<=cnt;i++)
    if(s[i].par){
        add(top[s[i].par],i);
    }
    cin>>m;
    for(int i=1,t1,t2;i<=m;i++){
        scanf("%d%d",&t1,&t2);
        add(cnt+t1,cnt+na+t2);
    }
    al=cnt+na+nb;
}
void tp(){
    queue<int>q;
    for(int i=1;i<=al;i++)if(!out[i])q.push(i);
    while(!q.empty()){
        int x=q.front();q.pop();
        if(x>cnt&&x<=cnt+na)dp[x]+=a[x-cnt].len;
        for(int i=head[x];i;i=e[i].nex){
            dp[e[i].v]=max(dp[e[i].v],dp[x]);
            if(!(--out[e[i].v]))q.push(e[i].v);
        }
    }
    for(int i=1;i<=al;i++)if(out[i]>0){puts("-1");return;}
    long long ans=0;
    for(int i=1;i<=al;i++)ans=max(ans,dp[i]);
    cout<<ans<<endl;
}
int main(){
    cin>>T;
    while(T--){
        Q();
        init();
        tp();
    }
    return 0;
}