P5284 [十二省联考 2019] 字符串问题

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 \leqslant i \leqslant n_a$）为 $A_i = S(la_i, ra_i)$。 类似地，Yazid 将划出 $n_b$ 个子串作为 $B$ 类串，第 $i$ 个（$1 \leqslant i \leqslant n_b$）为 $B_i = S(lb_i, rb_i)$。 现额外给定 $m$ 组支配关系，每组支配关系 $(x, y)$ 描述了第 $x$ 个 $A$ 类串**支配** 第 $y$ 个 $B$ 类串。 求一个**长度最大**的目标串 $T$，使得存在一个串 $T$ 的分割 $T = t_1+t_2+· · ·+t_k$（$k \geqslant 0$）满足： - 分割中的每个串 $t_i$ 均为 $A$ 类串：即存在一个与其相等的 $A$ 类串，不妨假设其为 $t_i = A_{id_i}$。 - 对于分割中所有相邻的串 $t_i, t_{i+1}$（$1 \leqslant i < k$），都有存在一个$A_{id_i}$ 支配的 $B$ 类串，使得该 $B$ 类串为 $t_{i+1}$ 的前缀。 方便起见，你只需要输出这个最大的长度即可。 特别地，如果存在无限长的目标串（即对于任意一个正整数 $n$，都存在一个满足限制的长度超过 $n$ 的串），请输出 $-1$。

无

无

#### 样例一解释 对于第 $1$ 组数据，$A$ 类串有 $\texttt{aaba}$ 与 $\texttt{aba}$，$B$ 类串有 $\texttt{aa}$，且 $A_2$ 支配 $B_1$。我们可以找到串 $\texttt{abaaaba}$，它可以拆分成 $A_2 + A_1$，且 $A_1$ 包含由 $A_2$ 所支配的 $B_1$ 作为前缀。可以证明不存在长度更大的满足限制的串。 对于第 $2$ 组数据，与第 $1$ 组数据唯一不同的是，唯一的 $B$ 类串为 $\texttt{a}$。容易证明存在无限长的满足限制的串。 对于第 $3$ 组数据，容易证明 $\texttt{abbaabbaaaabb}$ 是最长的满足限制的串。 #### 子任务 |$n_a$|$n_b$|$\lvert S\rvert$|测试点|$m$|$\lvert A_i\rvert \geq \lvert B_j\rvert$|其他限制| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$\leq 100$|$\leq 100$|$\leq 10^4$|$1$|$\leq 10^4$|保证|保证所有 $\lvert A_i\rvert,\lvert B_j\rvert\leq 100$| |$\leq 1000$|$\leq 1000$|$\leq 2\times 10^5$|$2\sim 3$|$\leq 2\times 10^5$|保证|无| |$=1$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$4$|$=n_b$|保证|无| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$5\sim 6$|$\leq 2\times 10^5$|保证|保证所有 $ra_i +1=la_{i+1}$| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$7\sim 8$|$\leq 2\times 10^5$|保证|无| |$\leq 2\times 10^5$|$\leq 2\times 10^5$|$\leq 2\times 10^5$|$9\sim 10$|$\leq 2\times 10^5$|不保证|无| 为了方便你的阅读，我们把**测试点编号**放在了表格的中间，请你注意这一点。 表格中的 $|A_i| > |B_j|$ 指的是**任意** $B$ 类串的长度不超过**任意** $A$ 类串的长度。 对于所有测试点，保证：$T \leqslant 100$，且对于测试点内所有数据，$|S|$, $n_a$, $n_b$, $m$ 的**总和**分别不会超过**该测试点中对应**的**单组数据的限制**的 $10$ 倍。比如，对于第 $1$ 组测试点，就有 $\sum n_a \leqslant 10 \times 100 = 1000$ 等。特别地，我们规定对于测试点 $4$，有 $T \leqslant 10$。 对于所有测试点中的每一组数据，保证：$1 \leqslant |S| \leqslant 2 \times 10^5$，$n_a$, $n_b \leqslant 2 \times 10^5$，$m \leqslant 2 \times 10^5$ #### 提示 十二省联考命题组温馨提醒您： **数据千万条，清空第一条。** **多测不清空，爆零两行泪。**