P11823 [湖北省选模拟 2025] 最后的台词 / lines

现某戏剧拟从一段优美的文字中截取若干片段作为剧本中的台词。具体的要求如下： 1. 剧本由若干句从给定文字中截取的台词组成。即，每句台词都必须是给定的字符串 $S$ 的一个子串。 2. 相邻的两句台词必须可以相互衔接。具体而言，给定一衔接系数 $k$，每一句台词的长度为 $k$ 的后缀必须和下一句台词的长度为 $k$ 的前缀相同。 3. 剧本最初的台词和最后的台词已经确定，第一句台词为 $S_{l_1\ldots r_1}$，最后一句台词为 $S_{l_2\ldots r_2}$。 现已知字符串 $S$，请你编写程序，对于多组给定的 $l_1, r_1, l_2, r_2$ 和衔接系数 $k$，计算是否存在满足上述限制的剧本。 如果存在，至少包含多少句台词。

无

无

**【样例 1 解释】** 对于第一组询问，给定的第一句台词和最后一句台词是完全相同的，因此剧本可以仅包含这一个字符串。 对于第二组询问，一种可行的方案为 $\{\text{ab}, \text{aba}, \text{ba}\}$。 对于第三组询问，一种可行的方案为 $\{\text{yaba}, \text{abax}\}$。 对于第四组询问，可以证明不存在可以满足题目中要求的剧本。 **【样例 2】** 见选手目录下的 `lines/lines2.in` 与 `lines/lines2.ans`。 样例 $2$ 满足测试点 $2\sim 3$ 的限制。 **【样例 3】** 见选手目录下的 `lines/lines3.in` 与 `lines/lines3.ans`。 样例 $3$ 满足测试点 $2\sim 3$ 的限制。 **【样例 4】** 见选手目录下的 `lines/lines4.in` 与 `lines/lines4.ans`。 样例 $4$ 满足测试点 $11\sim 12$ 的限制。 **【样例 5】** 见选手目录下的 `lines/lines5.in` 与 `lines/lines5.ans`。 样例 $5$ 满足测试点 $11\sim 12$ 的限制。 **【子任务】** 对于全部的测试数据，保证 $1 \le |S| \le 10^6$，$1 \le q \le 10^6$，$1 \le l_1 + k - 1 \le r_1 \le |S|$，$1 \le l_2 + k - 1 \le r_2 \le |S|$，$1 \le k \le |S|$。 | 测试点 | $\lvert S \rvert \leq$ | $q \leq $ | 特殊性质 | | :--: | :--: | :--: | :--: | | $1$ | $10$ | $10$ | 无 | | $2,3$ | $400$ | $400$ | 无 | | $4\sim 6$ | $3000$ | $5\times 10^4$ | 无 | | $7,8$ | $5\times 10^4$ | $5\times 10^4$ | $l_1 \le l_2$ | | $9,10$ | $5\times 10^4$ | $5\times 10^4$ | $k \le 10$ | | $11,12$ | $5\times 10^4$ | $5\times 10^4$ | 无 | | $13\sim 16$ | $2\times 10^5$ | $2\times 10^5$ | 无 | | $17\sim 20$ | $10^6$ | $10^6$ | 无 |