Description

有一个字符串 $S$，有 $n_a$ 个 A 类串是其子串，有 $n_b$ 个 B 类串是其子串，另外有 $m$ 个支配关系，表示第 $x$ 个 A 类串支配第 $y$ 个 B 类串。

求一个长度最大的字符串 $T$，需要满足两个条件：

  • 其可以分割为若干个 A 类串；
  • 不妨设 $T=t_1+t_2+t_3+…+t_k$，$t_i=A_{id_i}$，那么对于所有的 $t_i,t_{i+1}$，都存在一个 $A_{id_i}$ 支配的 B 类串，使得这个 B 类串是 $t_{i+1}$ 的前缀。

只需要输出长度的最大值即可，若可以无限长，输出 $-1$。

$|S|,n_a,n_b,m\leq2\times10^5$，多组数据，每个数据点中 $|S|,n_a,n_b,m$ 的总和不会超过单组数据限制的 $10$ 倍。

Solution

看到这个要求的东西以及这个支配关系，很容易想到尝试用图论模型描述这个题。

对于每个 A 类串，向其支配的 B 类串连边权为 A 类串长度的边，对于每个 B 类串，连向所有以这个 B 类串为前缀的 A 类串，边权为 $0$，这样目标串就对应这个图上的一个最长路再加上终点 A 类串的长度。

或者把 A 类串看作点权，求一个点权最大的路径。

暴力连是 $O(n^3)$，然后可以考虑用一个后缀数据结构，发现后缀树可以比较好描述这个东西。

我们找到每个 A 类串和 B 类串，对于支配关系直接连边，然后对于每个 B 类串，向其子树里所有 A 类串连边就好了。

这样是 $O(n^2)$ 的。

然后找到 A 类串和 B 类串这件事可以用倍增找：找到一个子串 $S[l:r]$，找到后缀 $l$ 在后缀树上对应的叶子结点，然后往上跳即可。这是 $O(n\log n)$ 的。

连边的话可以利用现成的后缀树，后缀树相当于已经帮我们连好边了。这是 $O(n)$ 的。

然后还有个问题是后缀树上的点是压缩过的，当同一个点对应长度不同的子串的时候，我们需要把它拆开，从长度小连向长度大即可。

需要注意的是，这么折腾完之后我们原来图上 A 连 B、B 连 A 的性质被破坏了，因此不能用上面说的点权的方法求答案，只能用边权来求。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cctype>
using namespace std;

namespace solve
{
    const int maxn = 1e6 + 10;
    typedef long long ll;

    int read(int &x)
    {
        x = 0;
        char ch = getchar();
        for (; !isdigit(ch); ch = getchar())
            ;
        for (; isdigit(ch); ch = getchar())
            x = x * 10 + ch - '0';
        return x;
    }

    inline int lg(int x) { return 31 - __builtin_clz(x); }

    int tot = 1, ch[maxn][26], father[maxn], mx[maxn], id[maxn], lst = 1;

    void insert(int c, int i)
    {
        int p = ++tot, f = lst;
        lst = p, id[i] = p, mx[p] = mx[f] + 1;
        while (f && !ch[f][c])
            ch[f][c] = p, f = father[f];
        if (f == 0)
            father[p] = 1;
        else
        {
            int q = ch[f][c];
            if (mx[q] == mx[f] + 1)
                father[p] = q;
            else
            {
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof(ch[q])), father[nq] = father[q], mx[nq] = mx[f] + 1;
                father[p] = father[q] = nq;
                while (f && ch[f][c] == q)
                    ch[f][c] = nq, f = father[f];
            }
        }
    }

    namespace dag
    {
        struct edge
        {
            int y, w;
        };
        vector<edge> e[maxn];
        int rd[maxn];
        inline void add(int x, int y, int w) { e[x].push_back({y, w}), rd[y]++; }

        ll f[maxn];
        int val[maxn];
        
        ll dp()
        {
            queue<int> q;
            for (int i = 1; i <= tot; i++)
                if (!rd[i])
                    q.push(i);
            while (!q.empty())
            {
                int x = q.front();
                q.pop();
                for (auto k : e[x])
                {
                    int v = k.y, w = k.w;
                    f[v] = max(f[v], f[x] + w);
                    if (--rd[v] == 0)
                        q.push(v);
                }
            }
            for (int i = 1; i <= tot; i++)
                if (rd[i])  
                    return -1;
            for (int i = 1; i <= tot; i++)
                f[i] += val[i];
            return *max_element(f + 1, f + 1 + tot);
        }
    }

    vector<int> e[maxn];
    int dep[maxn], ff[maxn][20];
    void build()
    {
        for (int i = 2; i <= tot; i++)
            e[father[i]].push_back(i);
    }

    void dfs1(int x, int fa)
    {
        dep[x] = dep[fa] + 1, ff[x][0] = fa;
        for (int i = 1; i <= 18; i++)
            ff[x][i] = ff[ff[x][i - 1]][i - 1];
        for (int v : e[x])
            dfs1(v, x);
    }

    vector<pair<int, int>> a[maxn]; // first : len, second : i

    inline int jump(int x, int len)
    {
        for (int i = lg(dep[x]); i >= 0; i--)
            if (mx[ff[x][i]] >= len)
                x = ff[x][i];
        return x;  
    }

    char str[maxn];
    int n, m;
    pair<int, int> seg[maxn];
    int p[maxn];

    void dfs(int x, int fa)
    {
        if (fa)
            dag::add(fa, x, 0);
        sort(a[x].begin(), a[x].end());
        a[x].erase(unique(a[x].begin(), a[x].end()), a[x].end());
        int lst = x;
        for (int i = 1; i < (int)a[x].size(); i++)
        {
            if (a[x][i].first != a[x][i - 1].first)
                dag::add(lst, ++tot, 0), lst = tot;
            p[a[x][i].second] = lst;
        }
        for (int v : e[x])
            dfs(v, lst);
    }

    void clear()
    {
        for (int i = 1; i <= tot; i++)
            dag::rd[i] = dag::f[i] = 0, dag::e[i].clear(), dag::val[i] = 0;
        for (int i = 1; i <= tot; i++)
            a[i].clear(), p[i] = 0, memset(ch[i], 0, sizeof(ch[i])), father[i] = id[i] = mx[i] = 0;
        for (int i = 1; i <= tot; i++)
            e[i].clear(), dep[i] = 0, memset(ff[i], 0, sizeof(ff[i]));
        lst = tot = 1;
    }

    void main()
    {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        for (int i = len; i >= 1; i--)
            insert(str[i] - 'a', i);
        build(), dfs1(1, 0);
        read(n);
        for (int i = 1; i <= n; i++)
            read(seg[i].first), read(seg[i].second);
        read(m);
        for (int i = n + 1; i <= n + m; i++)
            read(seg[i].first), read(seg[i].second);
        for (int i = 1; i <= n + m; i++)
        {
            p[i] = jump(id[seg[i].first], seg[i].second - seg[i].first + 1);
            a[p[i]].emplace_back(seg[i].second - seg[i].first + 1, i);
        }
        dfs(1, 0);
        for (int i = 1; i <= n; i++)
            dag::val[p[i]] = seg[i].second - seg[i].first + 1;
        int k;
        read(k);
        for (int i = 1; i <= k; i++)
        {
            int x, y;
            read(x), read(y), dag::add(p[x], p[y + n], seg[x].second - seg[x].first + 1);
        }
        cout << dag::dp() << endl;
        clear();
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--)
        solve::main();
}