分析
容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。
第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。
对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向子树中所有 A 类串对应的节点连边。找某个子串在 SAM 上的点可以记一下每个后缀对应的点然后在 Parent 树上倍增。
进一步，我们可以在 Parent 树上从上往下连边，由 Parent 树上的节点连向 B 类串，再从 B 类串连向 Parent 树上的子节点和子节点包含的 A 类串。
然而这样子有一个问题，就是 SAM 上每个节点可能包含了多个 A 类串、B 类串。于是我们把每个节点对应的串按长度排序，如果长度相同则把 B 类串放在前面，然后依次扫过去，并记一个 $p$ 为之前扫到过的最后一个的 B 类串（没有扫到 B 类串时则为 SAM 上的节点），从 $p$ 向当前扫到的节点连边即可。连出来大概是一个这样的东西
X → A1,A2
↓
B1
↓
B2 → A3最后的 $p$ 向 Parent 树上的子节点连边即可。
因为懒所以每次都暴力把整个数组清空了，于是跑得非常的慢。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mset(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=800000+10;
int n,na,nb,m; char s[N];
namespace S {
int lst,tot;
int fa[N],ch[N][26],len[N],pos[N],f[20][N];
void extend(int c) {
int p=lst,np=++tot; lst=np,len[np]=len[p]+1;
for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if (!p) fa[np]=1;
else {
int q=ch[p][c];
if (len[p]+1==len[q]) fa[np]=q;
else {
int nq=++tot; len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
int jump(int u,int l) {
for (int i=19;~i;--i)
if (len[f[i][u]]>=l) u=f[i][u];
return u;
}
void clear() {
mset(fa,0),mset(ch,0),mset(len,0),mset(pos,0),mset(f,0);
}
}
int tot;
int ed[N],ida[N],idb[N],isa[N],len[N],deg[N];
ll dp[N];
vector<int> E[N],vs[N];
queue<int> Q;
int main() {
int T=read();
while (T--) {
scanf("%s",s+1); n=strlen(s+1);
S::lst=S::tot=1;
for (int i=n;i;--i) S::extend(s[i]-'a'),S::pos[i]=S::lst;
for (int i=1;i<=S::tot;++i) S::f[0][i]=S::fa[i];
for (int i=1;i<=19;++i)
for (int j=1;j<=S::tot;++j) S::f[i][j]=S::f[i-1][S::f[i-1][j]];
tot=S::tot;
na=read();
for (int i=1;i<=na;++i) {
int l=read(),r=read(),u=S::jump(S::pos[l],r-l+1);
ida[i]=++tot,isa[tot]=1,len[tot]=r-l+1;
vs[u].emplace_back(tot);
}
nb=read();
for (int i=1;i<=nb;++i) {
int l=read(),r=read(),u=S::jump(S::pos[l],r-l+1);
idb[i]=++tot,isa[tot]=0,len[tot]=r-l+1;
vs[u].emplace_back(tot);
}
m=read();
for (int i=1;i<=m;++i) {
int u=read(),v=read();
E[ida[u]].emplace_back(idb[v]);
}
for (int i=1;i<=S::tot;++i) {
sort(vs[i].begin(),vs[i].end(),[](int i,int j) {
return len[i]<len[j]||(len[i]==len[j]&&!isa[i]&&isa[j]);
});
int p=i;
for (int j:vs[i]) {
E[p].emplace_back(j);
if (!isa[j]) p=j;
}
ed[i]=p;
}
for (int i=2;i<=S::tot;++i) E[ed[S::fa[i]]].emplace_back(i);
for (int i=1;i<=tot;++i)
for (int j:E[i]) ++deg[j];
for (int i=1;i<=tot;++i)
if (!deg[i]) Q.push(i),dp[i]=isa[i]*len[i];
while (!Q.empty()) {
int u=Q.front(); Q.pop();
for (int v:E[u]) {
dp[v]=max(dp[v],dp[u]+isa[v]*len[v]);
if (!--deg[v]) Q.push(v);
}
}
int flag=0;
for (int i=1;i<=tot;++i)
if (deg[i]) { flag=1; break; }
if (flag) puts("-1");
else {
ll ans=0;
for (int i=1;i<=tot;++i) ans=max(ans,dp[i]);
printf("%lld\n",ans);
}
S::clear();
mset(ed,0),mset(ida,0),mset(idb,0),mset(isa,0),mset(len,0),mset(deg,0),mset(dp,0);
for (int i=1;i<=tot;++i) E[i].clear();
for (int i=1;i<=S::tot;++i) vs[i].clear();
}
return 0;
}