[DS记录]P5284 [十二省联考2019]字符串问题
command_block
·
·
个人记录
看了看去年暑假的代码,发现看不懂了,于是补一篇Blog。
题意 : 给出一个字符串 S
指定两类若干个子串 A_{1...n_a},B_{1...n_b}。
有 m 组有向支配关系 x\rightarrow y ,表示 A_x 支配 B_y。
求一个字符串序列 T_{1...k} ,满足任意一个 T_i 都与某个 A 串相同 ,设为 A_{id_i}。
对于相邻的 T_i,T_{i+1} ,都要满足存在一个被 A_{id_i} 支配的 B 串,为 T_{i+1} 的前缀。
求该字符串序列的最大长度总和,或指出可以无限长。
------------
这肯定是一道字符串题,但“支配关系”感觉和图论又有隐约的联系。
注意到对字符串序列的要求只会涉及到相邻的两个串,很像“路径”。
实际上,我们可以将其抽象为这样的问题 :
对每组支配关系,连边 $A_x\rightarrow B_y$ 。若 $B_x$ 是 $A_y$ 的前缀,则连边 $B_x\rightarrow A_y$。
给 $A_x$ 赋权 $|A_x|$ ,要求出一条路径使得经过的点权和最大。
先解决子问题 : 给出一张有点权的有向图,求出一条路径使得经过的点权和最大。
能够发现,(本题中)若图不是`DAG`,则长度可以达到 $\inf$。
否则,在`DAG`上`DP`即可,具体实现时可以写拓扑排序。
接下来就是如何建立这张图。
支配关系是输入给出的,并不多,可以直接连边。而前缀关系可能有很多,我们需要优化建边。
不难发现,在后缀树上,祖先节点表示的串是儿子节点的前缀,那么 $B_x$ 就应该向子树内的所有 $A$ 串连边。
那么我们使用(外向)后缀树优化建边,就能实现每次连边到一颗子树了。
**结论** : 反串的 $\rm SAM$ 的$\rm parent$树就是原串的后缀树。
建立后缀树之后,还要在上面定位子串,方法和 $\rm SAM$ 相同:
从某个前缀节点开始向上跳,直到 $len$ 区间包含该子串为止。利用 $len$ 的单调性,不难使用倍增优化。
首先把每个子串定位好,然后从上到下连边,跑个拓扑排序……诶怎么过不去样例?
注意,我们手中的后缀树是压缩的。也就是说,每个点不仅仅表示一个字符串,而是压缩前后缀树中,不分叉父边上的所有串(蓝色部分)。
如图:
而这条蓝色的边也是有顺序的! 排在上面的才能转移到下面,逆着来是布星的。
所以,我们对于每个点内部,还要排序+二分来区别顺序。注意到长度短的点在上面,可以按照长度为序。
我比较懒就用了`std::map`,常数有点大。
具体实现中,由于$A$串之间不能连边,还需要拆成出入点限制回头,顺便把点权塞在中间。
复杂度是一个 $\log$ 的。
不错,写到这里终于能看懂代码了 (
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define ll long long
#define MaxN 205000
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Node
{int t[26],f,len;}a[MaxN<<1];
int tn,las,edp[MaxN];
void add(int c)
{
int np=++tn,p=las;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tn;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
vector<int> g[MaxN*5],l[MaxN*5];
int f[MaxN<<1][17];
void pfs(int u){
for (int i=0;i<g[u].size();i++){
f[g[u][i]][0]=u;
pfs(g[u][i]);
}
}
int findp(int p,int sl){
p=edp[p];
int k=16;
while(k--)
while(a[f[p][k]].len>=sl)
p=f[p][k];
return p;
}
#define fir first
#define sec second
map<int,int> sp[MaxN<<1];int tot;
int ab[MaxN<<1],len;
void getp(int n,int *tp)
{
for (int i=1,sl,edp;i<=n;i++){
edp=len-read()+1;
sl=len-read()+1;
sl=edp-sl+1;
tp[i]=findp(edp,sl);
if (!sp[tp[i]].count(sl)){
sp[tp[i]][sl]=++tot;
tp[i]=tot;
}else tp[i]=sp[tp[i]][sl];
}
}
int du[MaxN*5];
#define pb push_back
void adl(int f,int t,int len)
{du[t]++;g[f].pb(t);l[f].pb(len);}
int st,in[MaxN<<1],out[MaxN<<1];
pair<int,int> t[MaxN<<1];
void build()
{
for (int i=1;i<=tn;i++){
if (sp[i].empty()){
in[i]=out[i]=++tot;
continue;
}
map<int,int>::iterator it=sp[i].begin();
int cnt=0;
for (;it!=sp[i].end();it++)t[++cnt]=*it;
in[i]=t[1].sec+st;
out[i]=t[cnt].sec+st;
for (int i=1;i<=cnt;i++)
if (ab[t[i].sec]==1)
adl(t[i].sec+st,t[i].sec,t[i].fir);
for (int i=1;i<cnt;i++)
adl(t[i].sec+st,t[i+1].sec+st,0);
}
for (int i=2;i<=tn;i++)
adl(out[a[i].f],in[i],0);
}
queue<int> q;
ll dis[MaxN*5];
void topu()
{
for (int i=1;i<=tot;i++){
if (!du[i])q.push(i);
dis[i]=0;
}
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0,v;i<g[u].size();i++){
du[v=g[u][i]]--;
dis[v]=max(dis[v],dis[u]+l[u][i]);
if (!du[v])q.push(v);
}
}
bool flag=0;
for (int i=1;i<=tot;i++)
if (du[i]){flag=1;du[i]=0;}
if (flag){puts("-1");return ;}
ll ans=0;
for (int i=1;i<=tot;i++)ans=max(ans,dis[i]);
printf("%lld\n",ans);
}
int na,nb,m,ta[MaxN],tb[MaxN];
char str[MaxN];
void solve()
{
memset(a,0,sizeof(Node)*(tn+5));
for (int i=1;i<=tn;i++)sp[i].clear();
for (int i=1;i<=tot;i++)
{g[i].clear();l[i].clear();}
tot=0;tn=las=1;
scanf("%s",str+1);len=strlen(str+1);
reverse(str+1,str+len+1);
for (int i=1;i<=len;i++)
{add(str[i]-'a');edp[i]=las;}
for (int i=2;i<=tn;i++)
g[a[i].f].pb(i);
pfs(1);
for (int i=1;i<=tn;i++)g[i].clear();
for (int j=1;j<16;j++)
for (int i=1;i<=tn;i++)
f[i][j]=f[f[i][j-1]][j-1];
na=read();getp(na,ta);
nb=read();getp(nb,tb);
for (int i=1;i<=nb;i++)ab[tb[i]]=2;
for (int i=1;i<=na;i++)ab[ta[i]]=1;
st=tot;tot*=2;
build();
m=read();
for (int i=1,x,y;i<=m;i++){
x=read();y=read();
adl(ta[x],tb[y]+st,0);
}topu();
}
int main()
{
int T=read();
while(T--)solve();
return 0;
}
```