没看题解给做出来了，说明自己还有点水平。
先考虑下前40分怎么搞一个$O(n_a\times n_b)$的算法出来。
我们可以枚举每一个B串，然后看一下这个B串是哪些A串的前缀，设以B串$b_0$为前缀的A串集合为$A(b_0)$。
我们对于每一个A串建立一个点，设第$i$个A串对应的点为$a_i$，点权为这个A串的长度。
对于一条支配关系$(x,y)$，我们把$a_x$向$A(b_y)$中的所有点连边。
最后新建一个起点，这个起点向所有的A串的点连边，然后跑以这个点为起点的最长路即可。
如果遇到环，那么这个环一定是正环(我们没有建立0权点)，就说明存在无限长的合法串。
如何判断一个$B$串是不是另一个$A$串的前缀？哈希。
复杂度$O(n_a\times n_b)$，没有任何优化的空间。
40分。
可惜在考场上我连这40分都没有。
考虑换一种思路，比如后缀数组？
搞出来串S的后缀数组，定位到一个B串是哪一个后缀的前缀，然后直接二分出来往左往右到哪个位置仍然是以这个B串为前缀，然后向这个区间内长度比这个B串长的A串连边。
直接做还是$O(n^2)$的，主席树优化建图可以搞到$O(nlogn)$。
然而我不会后缀数组
再换一种思路，比如SAM?
后缀链接树上，任何一个点表示的字符串都一定是它子树内的点表示的串的严格后缀。
然而我们现在要求出来有哪些A串是一个B串的前缀。
所以把S串翻转一下，就变成了哪些A串是一个B串的后缀了。
我们通过树上倍增的方式在后缀链接树上定位到所有的A串和B串。
一个B串被挂到了点vtx上，就说明vtx上长度不小于A的串，和vtx子节点里面的所有串，都以B为后缀。
我们再把所有的A串挂到后缀链接树上，然后对于每个A串新建一个两个点v1和v2，v2的点权为这个A串的长度，同时v1有向v2的边。
然后假设点vtx有A串被挂上去了，那么首先把vtx拆成in和out两个点，out的出边为原先vtx的出边，in的入边为原先vtx的入边，同时in向out连一条边。
对于挂在vtx上的每一个A串，我们把他们按照长度从小到大排序，设vtx上的第i个A串为$vtx_A(i)$，那么我们首先把in向$vtx_A(i).v1$连边（表示走到这个点后可以选择这个A
串），然后把$vtx_A(i).v1$向$vtx_A(i+1).v1$连边，代表选择了一个长度小的A串后，选择长度比它大的也一定合法。
然后再考虑B串，设点$vtx$上的第$i$个B串为$vtx_B(i)$，我们仍然建立点$v1$和$v1$，然后找到长度大于等于vtx_B(i)且在同一个点上的长度最小的A串$a_0$，然后从$vtx_B(i).v1$向$a_0.v1$连边，代表这个B串是这个点上长度大于等于它的A串的后缀，然后$v2$向$vtx.out$连边，代表这个B串是子树内所有A串的后缀。
然后考虑支配关系，对于一个支配关系$(a,b)$，定位到A所对应的$v2$点和b所对应的$v1$点(表示从A串a下面可以接以B串b为后缀的所有A串)，连边即可。
然后跑DAG上的最长路，如果存在环说明有无限长的合法串。
树上倍增不要写错了，注意树高的处理。
倍增的2的幂的上界为$ceil(maxdepth)$，其中maxdepth为树最深的深度，从0开始。
#include <assert.h>
#include <inttypes.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 5e5;
void* allocate();
int_t id = 0;
struct Node {
int_t sufID;
int_t max;
Node* link = nullptr;
Node* chds[26];
int_t id;
Node(int_t max) {
this->max = max;
memset(chds, 0, sizeof(chds));
sufID = -1;
id = ++::id;
}
Node*& access(char chr) { return chds[chr - 'a']; }
Node* clone() {
Node* next = new (allocate()) Node(*this);
next->id = ++::id;
next->sufID = -1;
return next;
}
};
int_t used = 0;
char buf[LARGE * 10 * sizeof(Node)];
void* allocate() { return buf + (used++) * sizeof(Node); }
Node* append(Node* root, Node* last, char chr, int_t sufID) {
Node* next = new (allocate()) Node(last->max + 1);
next->sufID = sufID;
Node* curr = last;
while (curr && curr->access(chr) == nullptr) {
curr->access(chr) = next;
curr = curr->link;
}
if (curr == nullptr) {
next->link = root;
} else if (curr->access(chr)->max == curr->max + 1) {
next->link = curr->access(chr);
} else {
Node* oldNode = curr->access(chr);
Node* newNode = oldNode->clone();
oldNode->link = next->link = newNode;
newNode->max = curr->max + 1;
while (curr && curr->access(chr) == oldNode) {
curr->access(chr) = newNode;
curr = curr->link;
}
}
return next;
}
char str[LARGE + 10];
//某个后缀对应的SAM节点
Node* sufs[LARGE + 1];
int_t len, na, nb, m;
Node* root;
int_t jump[25][LARGE + 1], depth[LARGE + 1];
int_t val[LARGE * 10 + 1];
Node* nodes[LARGE + 1];
std::vector<int_t> graph[LARGE * 10 + 1];
void DFS0(int_t vtx) {
for (int_t to : graph[vtx]) {
jump[0][to] = vtx;
depth[to] = depth[vtx] + 1;
DFS0(to);
}
}
//某个节点向上跳2^k到哪里
void DFS1(int_t vtx, int_t k) {
if ((1 << k) > depth[vtx])
jump[k][vtx] = -1;
else {
jump[k][vtx] = jump[k - 1][jump[k - 1][vtx]];
}
for (int_t to : graph[vtx]) DFS1(to, k);
}
bool inStack[LARGE * 10 + 1];
int64_t memory[LARGE * 10 + 1];
bool visited[LARGE * 10 + 1];
int64_t DFS(int_t vtx) {
if (inStack[vtx]) return -1;
if (visited[vtx]) return memory[vtx];
inStack[vtx] = true;
auto& result = memory[vtx];
result = val[vtx];
visited[vtx] = true;
for (auto to : graph[vtx]) {
auto x = DFS(to);
if (x == -1) return -1;
result = std::max(result, val[vtx] + x);
}
inStack[vtx] = false;
return result;
}
int64_t process() {
scanf("%s", str + 1);
len = strlen(str + 1);
Node* last = root = new (allocate()) Node(0);
for (int_t i = len; i >= 1; i--) {
last = append(root, last, str[i], i);
sufs[i] = last;
}
//构建后缀树
for (int_t i = 1; i < id; i++) {
auto ptr = (Node*)(buf + sizeof(Node) * i);
graph[ptr->link->id].push_back(ptr->id);
}
for (int_t i = 0; i < used; i++) {
Node* ptr = (Node*)(buf + i * sizeof(Node));
nodes[ptr->id] = ptr;
}
depth[1] = 0;
DFS0(root->id);
int_t maxdepth = *std::max_element(depth + 1, depth + 1 + id);
const int_t SIZE2 = ceil(log2(maxdepth));
for (int_t i = 1; i <= SIZE2; i++) DFS1(root->id, i);
//从node开始向上跳，直到跳到某个点存在长度为len的子串
//返回编号
const auto jumpup = [&](int_t vtx, int_t len) {
for (int_t i = SIZE2; i >= 0; i--) {
auto node = nodes[vtx];
if (len >= node->link->max + 1 && len <= node->max) break;
if (jump[i][vtx] <= 0 || nodes[jump[i][vtx]]->link == nullptr) {
continue;
}
if (nodes[jump[i][vtx]]->max >= len) vtx = jump[i][vtx];
}
assert(len >= nodes[vtx]->link->max + 1 && len <= nodes[vtx]->max);
return vtx;
};
//每个A和B对应的后缀树节点编号
static int_t A[LARGE + 1], B[LARGE + 1];
//每个AB对应的子串
using pair_t = std::pair<int_t, int_t>;
static pair_t As[LARGE + 1], Bs[LARGE + 1];
//每个A B串对应的辅助节点的编号
static int_t Aaux[LARGE + 1], Baux[LARGE + 1];
struct SString {
int_t type;
int_t id;
int_t len;
int_t v1, v2;
};
//每个节点上挂的A和B的编号
static std::vector<SString> strings[LARGE + 1];
for (int_t i = 1; i <= id; i++) {
strings[i].clear();
}
scanf("%d", &na);
int_t minlen = len;
for (int_t i = 1; i <= na; i++) {
int_t left, right;
scanf("%d%d", &left, &right);
A[i] = jumpup(sufs[left]->id, right - left + 1);
strings[A[i]].push_back(SString{1, i, right - left + 1});
As[i] = pair_t(left, right);
minlen = std::min(minlen, right - left + 1);
}
scanf("%d", &nb);
for (int_t i = 1; i <= nb; i++) {
int_t left, right;
scanf("%d%d", &left, &right);
B[i] = jumpup(sufs[left]->id, right - left + 1);
strings[B[i]].push_back(SString{2, i, right - left + 1});
Bs[i] = pair_t(left, right);
// assert(right - left + 1 <= minlen);
}
//每个点的挂的子串按照长度从小到大排序,长度相同的，B串排在前面。
int_t id0 = id;
// 1号点没必要搞
for (int_t i = 2; i <= id0; i++) {
auto& curr = strings[i];
std::sort(curr.begin(), curr.end(),
[](const SString& a, const SString& b) {
if (a.len == b.len)
return b.type < a.type;
else
return a.len < b.len;
});
//新建一个点，用来代替出边
int_t out = ++id;
//把原来的出边全都改成从out出发
for (int_t to : graph[i]) graph[out].push_back(to);
graph[i].clear();
graph[i].push_back(out);
int_t last = -1;
for (int_t j = 0; j < (int)curr.size(); j++) {
//每个A串或B串建两个点，一个统计权值,另一个拿来往下走
int_t v1 = ++id;
int_t v2 = ++id;
graph[i].push_back(v1);
graph[v1].push_back(v2);
curr[j].v1 = v1;
curr[j].v2 = v2;
//只有B类才可以不走支配边，直接沿着后缀链接树往下走
// A类点必须走支配边
if (curr[j].type == 1)
Aaux[curr[j].id] = v2;
else if (curr[j].type == 2)
Baux[curr[j].id] = v1;
if (curr[j].type == 1) {
val[v2] = curr[j].len;
}
// B类点才可以接着往子树走
if (curr[j].type == 2) {
graph[v2].push_back(out);
continue;
}
if (last != -1) {
//每个A类点向比他长的连边，代表可以选这个也可以选比他长的
graph[last].push_back(v1);
}
last = v1;
}
for (int_t j = 0; j < curr.size(); j++) {
if (curr[j].type == 2) {
if (j + 1 < curr.size()) {
//把B类点插到A类的中去
graph[curr[j].v1].push_back(curr[j + 1].v1);
}
}
}
}
scanf("%d", &m);
for (int_t i = 1; i <= m; i++) {
int_t a, b;
scanf("%d%d", &a, &b);
graph[Aaux[a]].push_back(Baux[b]);
}
auto result = DFS(root->id);
memset(visited + 1, 0, sizeof(visited[0]) * id);
memset(inStack + 1, 0, sizeof(inStack[0]) * id);
memset(val + 1, 0, sizeof(val[0]) * id);
used = 0;
for (int_t i = 1; i <= id; i++) graph[i].clear();
id = 0;
return result;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
cout << process() << endl;
}
return 0;
}
