感觉这题 SA 做法绝对不止 \(\color{orange} *2300\)。
给出字符串 \(s\)，以及 \(m\) 个询问串 \(p_i\)，每次询问是否能找到两个不交的区间 \([a,b],[c,d]\) 使得 \(\overline{s_as_{a+1}\dots s_bs_cs_{c+1}\dots s_d} = p_i\)。
\(m\le 10^2\)，\(|p_i|\le10^3\)，\(|s|\le 10^5\)。
考虑将所有串拼成一个大串 \(S\)，做一遍后缀排序，求出 \(sa,rk,\text{height}\) 数组。
对于每一组询问，考虑枚举 \(j\) 表示找到 \([a,b],[c,d]\) 使得 \(\overline{s_as_{a+1}\dots s_b}=\overline{p_{i_1}p_{i_2}\dots p_{i_{j}}},\overline{s_bs_{c+1}\dots s_d}=\overline{p_{i_{j+1}}p_{i_{j+2}}\dots p_{i_{|p_i|}}}\)。可以通过二分 + ST 表求出满足条件的后缀的排名区间。
我们考虑选择最左边的 \([a,b]\) 以及最右边的 \([c,d]\)，这样一定不劣。因此考虑以排名为下标建立 ST 表维护某个排名区间内，\(\boldsymbol{\le |s|}\) 的最左、左右后缀的位置。然后判断这两个位置截取出来的子串是否相交即可。
时间、空间复杂度均为 \(\mathcal{O}(|S|\log |S|)\)。