tag: 字符串

填完了。 ...

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$ 倍。 ...

前言 不能完全不管字符串，就硬着头皮学一学。 完全未完工。 ...

前言 最近字符串模拟赛中遇到了一道诡异的题，std 的方法是启发式合并 Trie 树，但我写了个更简单（？）的 BFS＋Trie树+LCA 做法。 后来得知是 CF 的题，就上来交一波，结果确实 AC 了。 这做法大概是对的，但是似乎有点慢（还难写）… ...