U150047 不考字符串 5

RT，不考字符串的第 5 道。 由 [@Aliemo](https://www.luogu.com.cn/user/187253) 提供。

给定两字符串 $S_1,S_2$，再给定 $n$ 个字符串 $T_1\sim T_n$。对于每个字符串 $T_i$，询问能否将 $T_i$ 拆分成三个字符串 $t_1,t_2,t_3$，满足： $$\begin{cases} t_1 + t_2 + t_3 = T_i\\ t_1\in S_1\\ t_2\in S_2\\ t_3\in S_1 \end{cases}$$ 若满足条件则输出 `1`，否则输出 `0`。 其中 $+$ 表示字符串的拼接，$t\in S$ 表示 $t$ 是 $S$ 的一个子串。

第 $1$ 行有一个字符串，代表 $S_1$。 第 $2$ 行有一个字符串，代表 $S_2$。 第 $3$ 行有一个整数 $n$，代表询问次数。 第 $4\sim n + 3$ 行每行一个字符串，代表一次询问。

输出共 $n$ 行。第 $i$ 行代表第 $i$ 次询问的结果。若满足条件则输出 `1`，否则输出 `0`。

$1\le n\le 10$，$1\le |S_1|,|S_2|,|T_i|\le 2\times 10^5$。 ## Sol 考虑先标记是 $S_1$ 的子串的 $T_i$ 的前后缀，可以直接用 KMP 求得。具体地，以前缀为例，在 $S_1$ 上匹配 $T_i$ 时，所有匹配长度的并集即为所有的合法前缀。对于合法后缀的标记，在 $S_1$ 的反串上匹配 $T_i$ 的反串即可。 再对 $S_2$ 建立 SAM，把 $T_i$ 扔到上面匹配。枚举到每个字符时，有对应转移函数就转移，否则跳 $\operatorname{link}$ 直到有对应转移函数。这样每次匹配的部分都是 $T_i$ 的一段**以枚举到的字符为结尾**的**最长**的子串，设它为 $T_i[l:r]$。 此时考察是否存在一种合法的拆分方案，满足 $t_2$ 的结尾是 $T_i[r]$。显然 $T_i[l:r]$ 的所有后缀都是 $S_2$ 的子串，则存在合法方案的条件是： - $T_i$ 的前缀 $T_i[1:l - 1] \sim T_i[1:r - 1]$ 是一个被标记过的前缀。 - $T_i$ 的后缀 $T_i[r + 1:n] $ 是一个被标记过的后缀。 在匹配过程中判断即可。总复杂度 $O(|S_1| + |S_2| + \sum |T_i|)$。 ## gen ```cpp //批量生产测试数据 /* By:fastle 用自己习惯的方式修改了代码。 生成 10 组 a+b problem 的数据。 */ #include using namespace std; #define LL long long #define problem "a" //输出文件名 #define prename "a" //更改之前的文件名 //============================================================= char ak[1000]; const int cases = 10; //数据组数 const int mode = 1; //1 造数据 // 2重新编号 int getrand() { return (rand()