洛谷 P5284 [十二省联考2019]字符串问题 题解【后缀自动机】【倍增】【拓扑排序】

作者: wjyyy 分类: 倍增,后缀自动机,图论,字符串,拓扑排序,解题报告 发布时间: 2019-05-08 21:21

点击量:35

考场上唯一一道弃掉的题。看来 SAM 还是挺好玩的

题目背景

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

对于一个字符串 $S$,我们定义 $|S|$ 表示 $S$ 的长度。

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

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

我们说一个字符串 $T$ 是 $S$ 的前缀,当且仅当 $S(1, |T|) = T$。

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

题目描述

现有一个字符串 $S$。

Tiffany 将从中划出 $n_a$ 个子串作为 A 类串,第 $i$ 个($1\le i\le n_a$)为 $A_i = S(la_i,ra_i)$。

类似地,Yazid 将划出 $n_b$ 个子串作为 $B$ 类串,第 $i$ 个($1\le i\le n_b$)为 $B_i = S(lb_i,rb_i)$。

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

求一个长度最大的目标串 $T$,使得存在一个串 $T$ 的分割 $T = t_1 +t_2 + \cdots +t_k$($k \ge 0$)满足:

  • 分割中的每个串 $t_i$ 均为 A 类串:即存在一个与其相等的 A 类串,不妨假设其为 $t_i = A_{id_i}$。

  • 对于分割中所有相邻的串 $t_i, t_{i+1}$($1\leq i < k$),都有存在一个 $A_{id_i}$ 支配的 B 类串,使得该 B 类串为 $t_{i+1}$ 的前缀。

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

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

输入格式

从标准输入中读入数据。

单个测试点中包含多组数据,输入的第一行包含一个非负整数 $T$ 表示数据组数。接下来依次描述每组数据,对于每组数据:

  • 第 $1$ 行一个只包含小写字母的字符串 $S$。

  • 第 $2$ 行一个非负整数 $n_a$,表示 A 类串的数目。接下来 $n_a$ 行,每行 $2$ 个用空格隔开的整数。

    • 这部分中第 $i$ 行的两个数分别为 $la_i,ra_i$,描述第 $i$ 个 A 类串。

    • 保证 $1\le la_i\le ra_i\le |S|$。

  • 接下来一行一个非负整数 $n_b$,表示 B 类串的数目。接下来 $n_b$ 行,每行 $2$ 个用空格隔开的整数。

    • 这部分中第 $i$ 行的两个数分别为 $lb_i,rb_i$,描述第 $i$ 个 B 类串。

    • 保证 $1\le lb_i\le rb_i\le|S|$。

  • 接下来一行一个非负整数 $m$,表示支配关系的组数。接下来 $m$ 行,每行 $2$ 个用空格隔开的整数。

    • 这部分中每行的两个整数 $x,y$,描述一对 $(x,y)$ 的支配关系,具体意义见【题目描述】。

    • 保证 $1\le x\le n_a$,$1\le y\le n_b$。保证所有支配关系两两不同,即不存在两组支配关系的 $x,y$ 相同。

输出格式

输出到标准输出中。

依次输出每组数据的答案,对于每组数据:

  • 一行一个整数表示最大串长。特别地,如果满足限制的串可以是无限长的,则请输出 $-1$。

样例 1 输入

3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1

样例 1 输出

7
-1
13

样例 1 解释

对于第 $1$ 组数据,$A$ 类串有 aabaaba,$B$ 类串有 aa,且 $A_2$ 支配 $B_1$。我们可以找到串 abaaaba,它可以拆分成 $A_2+A_1$,且 $A_1$ 包含由 $A_2$ 所支配的 $B_1$ 作为前缀。可以证明不存在长度更大的满足限制的串。

对于第 $2$ 组数据,与第 $1$ 组数据唯一不同的是,唯一的 $B$ 类串为 a。容易证明存在无限长的满足限制的串。

对于第 $3$ 组数据,容易证明 abbaabbaaaabb 是最长的满足限制的串。

样例 2

见选手目录下的 string/string2.instring/string2.ans

样例 3

见选手目录下的 string/string3.instring/string3.ans

样例 3 解释

这个测试点满足【子任务】中提到的 $\left|A_i\right|\ge \left|B_j\right|$ 的限制。

$n_a$ $n_b$ $\mid S\mid$ 测试点 $m$ $\left\vert A_i\right\vert\ge\left\vert B_j\right\vert$ 其他限制
$\le 100$ $\le 100$ $\le 10^4$ $1$ $\le 10^4$ 保证 保证所有 $\left\vert A_i\right\vert,\left\vert B_j\right\vert\le 100$
$\le 1000$ $\le 1000$ $\le 2\times 10^5$ $2\sim 3$ $\le 2\times 10^5$ 保证
$=1$ $\le 2\times 10^5$ $\le 2\times 10^5$ $4$ $=n_b$ 保证
$\le 2\times 10^5$ $\le 2\times 10^5$ $\le 2\times 10^5$ $5\sim 6$ $\le 2\times 10^5$ 保证 保证所有 $ra_i+1=la_{i+1}$
$\le 2\times 10^5$ $\le 2\times 10^5$ $\le 2\times 10^5$ $7\sim 8$ $\le 2\times 10^5$ 保证
$\le 2\times 10^5$ $\le 2\times 10^5$ $\le 2\times 10^5$ $9\sim 10$ $\le 2\times 10^5$ 不保证

为了方便你的阅读,我们把测试点编号放在了表格的中间,请你注意这一点。

表格中的 $\left|A_i\right|\ge \left|B_j\right|$ 指的是任意 B 类串的长度不超过任意 A 类串的长度。

对于所有测试点,保证:$T\le 100$,且对于测试点内所有数据,$|S|,n_a,n_b,m$ 的总和分别不会超过该测试点中对应的单组数据的限制的 $10$ 倍。比如,对于第 $1$ 组测试点,就有 $\sum n_a\le 10\times 100=1000$ 等。特别地,我们规定对于测试点 $4$,有 $T\le 10$。

对于所有测试点中的每一组数据,保证:$1\le |S|\le 2\times 10^5$,$n_a,n_b\le 2\times 10^5$,$m\le 2\times 10^5$。

提示

十二省联考命题组温馨提醒您:

数据千万条,清空第一条。

多测不清空,爆零两行泪。

题解:

首先弄懂 A, B 串的关系。A 串是可以出现在 $T$ 中的,B 串是辅助串,决定了 $A_i$ 能否和 $A_j$ 连在一起。

如果 $A_i$ 支配了 $A_j$ 的前缀 $B_k$,那么最终的串 $T$ 可以有一个子串 $A_i+A_j$。

考虑暴力怎么做。如果 $A_i$ 支配了 $B_j$,那么认为 $A_i$ 可以借助 $B_j$ 作为“跳板”,然后接上以 $B_j$ 为前缀的 $A_k$。从 $A_i$ 向它支配的 $B_j$ 连边;从 $B_j$ 向以它为前缀的 $A_k$ 连边,然后求最长路。

这时需要找到每个 $B_i$,以及每个 $B_i$ 是哪些 $A_i$ 的前缀。如果我们把原串 $S$ 翻转一下,那么原先的前缀就转为了后缀,考虑建立 $S$ 的后缀自动机,这样每个 A, B 串就都属于后缀自动机上的一个状态了。

下文中的所有变量均认为是翻转后的。

在读入所有的 $la_i,ra_i,lb_i,rb_i$ 之后,我们可以在 parent 树上定位每个串。对于一组 $l,r$,我们可以在后缀自动机上找到包含 $S(1,r)$ 的状态,那么 $S(l,r)$ 一定在它 parent 树的祖先上。这个操作可以倍增,倍增的转移条件控制一下 $mx$ 就可以了。

不过有时候一个节点会包含很多个后缀相同的串,如果直接拿这些点作为转移状态,就会出现一些转移问题,所以我们要考虑拆点。

当然,这和后缀自动机上的拆出 $nq$ 类点不同。此时整个后缀自动机中有用的部分只有 parent 树。因此把 $\to\bigcirc\to$ 拆成 $\to\circ\to\bullet\to\circ\to$,其中“$\bullet$”是我们想要的那个点;即把一个点拆成一条链放在原来的位置上。

由于 parent 树上一个节点 $a$ 的子树所代表的状态都以 $a$ 为后缀。如果一个串 $A_i$ 支配了 $a$,那么以 $a$ 为后缀的串 $A_j$ 就都可以接在 $A_i$ 后面。

所以如果存在一个串 $A_j$ 所代表的状态属于 $a$ 的子树,那么 $A_i$ 后面就可以接上 $A_j$ 了。

当 $A_i$ 支配了 $a$,则从 $A_i$(此时 $A_i$ 的点一定只包含这一个状态)连一条边到 $a$(由于 $a$ 是某个 $B_i$ 所属的节点,那么一定也只包含这一个状态),边权为 $|A_i|$,会在后面的拓扑排序用到。

我们以 parent 树的原树为基础建立有向图,原来的边从 $par_i$ 指向 $i$,边权为 $\bf 0$,表示一个点可以免费访问到子树内所有的点。再加上上面的边,就构成了一个有向图。

此时我们进行拓扑排序,如果队列右指针小于节点个数,说明图中有环,此时输出 $-1$;否则输出最长路。

时间复杂度 $O(|S|\log|S|)$,瓶颈主要在倍增(有一个排序是为了代码简洁)。

Code:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define gc getchar
#define par f[0]
using namespace std;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
char s[200100];
int ch[26][1200100],mx[1200100],f[21][1200100],pcnt,n;
void build()
{
    int p=pcnt=1;
    for(int i=1;i<=n;++i)
    {
        int w=s[i]-'a';
        int np=++pcnt;
        mx[np]=mx[p]+1;
        while(p&&!ch[w][p])
        {
            ch[w][p]=np;
            p=par[p];
        }
        if(!p)
            par[np]=1;
        else
        {
            int q=ch[w][p];
            if(mx[q]==mx[p]+1)
                par[np]=q;
            else
            {
                int nq=++pcnt;
                mx[nq]=mx[p]+1;
                while(p&&ch[w][p]==q)
                {
                    ch[w][p]=nq;
                    p=par[p];
                }
                for(int j=0;j<26;++j)
                    ch[j][nq]=ch[j][q];
                par[nq]=par[q];
                par[q]=par[np]=nq;
            }
        }
        p=np;
    }
}
struct qaq
{
    int ty,l,id;
    qaq(int ty,int l,int id)
    {
        this->ty=ty;
        this->l=l;
        this->id=id;
    }
    qaq(){}
    friend bool operator <(qaq a,qaq b)
    {
        return a.l<b.l;
    }
};
vector<qaq> d[200100];
vector<qaq> g[1200100];
void conf(int na,int ty)
{
    int u,v;
    for(int i=1;i<=na;++i)
    {
        u=n-read()+1;
        v=n-read()+1;
        d[u].push_back(qaq(ty,u-v+1,i));
    }
    int p=1;
    for(int i=1;i<=n;++i)
    {
        p=ch[s[i]-'a'][p];
        for(vector<qaq>::iterator it=d[i].begin();it!=d[i].end();++it)
        {
            int P=p;
            for(int j=20;j>=0;--j)
                if(mx[f[j][P]]>=it->l)
                    P=f[j][P];
            g[P].push_back(*it);
        }
        d[i].clear();
    }
}
int split(int p,int l)
{
    if(mx[p]==mx[par[p]]+1)
        return p;
    if(mx[p]==l)
    {
        int np=++pcnt;
        mx[np]=l-1;
        par[np]=par[p];
        par[p]=np;
        return p;
    }
    if(l==mx[par[p]]+1)
    {
        int np=++pcnt;
        mx[np]=l;
        par[np]=par[p];
        par[p]=np;
        return np;
    }
    int np=++pcnt;
    mx[np]=l-1;
    int nq=++pcnt;
    mx[nq]=l;
    par[np]=par[p];
    par[nq]=np;
    par[p]=nq;
    return nq;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[1400000];
int head[1200100],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
}
int in[1200100],a[1200100],b[1200100];
int Q[1200100];
long long F[1200100];
int main()
{
    #ifdef wjyyy
        freopen("a.in","r",stdin);
    #endif
    memset(head,-1,sizeof(head));
    int T=read();
    while(T--)
    {
        for(int i=1;i<=pcnt;++i)
        {
            in[i]=0;
            F[i]=0;
            head[i]=-1;
            for(int j=0;j<26;++j)
                ch[j][i]=0;
        }
        ecnt=-1;
        scanf("%s",s+1);
        n=strlen(s+1);
        reverse(s+1,s+1+n);
        par[1]=0;
        build();
        par[1]=1;
        for(int i=1;i<=20;++i)
            for(int j=1;j<=pcnt;++j)
                f[i][j]=f[i-1][f[i-1][j]];
        int na=read();
        conf(na,0);
        conf(read(),1);
        for(int i=1;i<=pcnt;++i)
        {
            sort(g[i].begin(),g[i].end());
            int lstl=0,lstans=0;
            for(vector<qaq>::iterator it=g[i].begin();it!=g[i].end();++it)
            {
                if(it->l==lstl)
                {
                    if(it->ty)
                        b[it->id]=lstans;
                    else
                        a[it->id]=lstans;
                    continue;
                }
                lstl=it->l;
                lstans=split(i,lstl);
                if(it->ty)
                    b[it->id]=lstans;
                else
                    a[it->id]=lstans;
            }
            g[i].clear();
        }
        for(int i=2;i<=pcnt;++i)
        {
            add(par[i],i,0);
            ++in[i];
        }
        int m=read(),u,v;
        for(int i=1;i<=m;++i)
        {
            u=read();
            v=read();
            add(a[u],b[v],mx[a[u]]);
            ++in[b[v]];
        }
        int l=0,r=0;
        Q[++r]=1;
        while(l<r)
        {
            int x=Q[++l];
            for(int i=head[x];~i;i=e[i].nxt)
            {
                F[e[i].n]=F[e[i].n]>F[x]+e[i].v?F[e[i].n]:F[x]+e[i].v;
                --in[e[i].n];
                if(!in[e[i].n])
                    Q[++r]=e[i].n;
            }
        }
        if(r<pcnt)
            puts("-1");
        else
        {
            long long ans=0;
            for(int i=1;i<=na;++i)
                ans=ans>F[a[i]]+mx[a[i]]?ans:F[a[i]]+mx[a[i]];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */