洛谷 P5284 [十二省联考2019]字符串问题 题解【后缀自动机】【倍增】【拓扑排序】
点击量：293
考场上唯一一道弃掉的题。看来 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$ 类串有
aaba与aba，$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.in与string/string2.ans。样例 3
见选手目录下的
string/string3.in与string/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;
}
说点什么