P11291 【MX-S6-T3】「KDOI-11」简单的字符串问题 2
题目背景
原题链接：。
题目描述
给定 $n$ 个字符串 $S_1, \ldots, S_n$ 以及一个字符串 $T$。
对于一个字符串 $R$，定义 $|R|$ 表示 $R$ 的长度、$R_{[l,r]}$ 表示 $R$ 的第 $l\sim r$ 个字符组成的字符串。字符串 $R'$ 是字符串 $R$ 的前缀当且仅当存在 $1\leq p\leq |R|$ 且 $p$ 为整数使得 $R'=R_{[1,p]}$。
定义一个字符串 $R$ 是**好的**当且仅当它是某个 $S_i$ 的前缀**或** $R$ **为空**。
对于若干字符串 $R_1,R_2,\dots,R_k$，定义 $R_1+R_2+\dots+R_k$ 为 $R_1,R_2,\dots,R_k$ 顺次拼接得到的字符串。
定义一个三元组 $(l,r,k)$（$l,r,k$ 均为整数）是好的当且仅当 $1\leq l\leq r\leq|T|$，$1\leq k\leq K$ 且存在 $k$ 个**好的**字符串 $R_1,R_2,\dots,R_k$ 使得 $R_1+R_2+\dots+R_k=T_{[l,r]}$。
请你求出好的三元组的数量，并对于每个 $i$ 求出有多少好的三元组 $(l,r,k)$ 满足 $l\leq i\leq r$。如果你只能求出两者中其一，也可以获得部分分数，见【**输出格式**】。
输入格式
无
输出格式
无
说明/提示
**【样例解释 #1】**
符合要求的 $(l,r,k)$ 有以下 $13$ 组：
* $(1,1,1)$；
* $(1,1,2)$；
* $(1,2,1)$；
* $(1,2,2)$；
* $(1,3,2)$；
* $(3,3,1)$；
* $(3,3,2)$；
* $(3,4,2)$；
* $(3,5,2)$；
* $(4,4,1)$；
* $(4,4,2)$；
* $(4,5,1)$；
* $(4,5,2)$。
**【样例 #4】**
见附件中的 `string/string4.in` 与 `string/string4.ans`。
该组样例满足测试点 $1\sim3$ 的约束条件。
**【样例 #5】**
见附件中的 `string/string5.in` 与 `string/string5.ans`。
该组样例满足测试点 $4\sim6$ 的约束条件。
**【样例 #6】**
见附件中的 `string/string6.in` 与 `string/string6.ans`。
该组样例满足测试点 $7\sim10$ 的约束条件。
**【样例 #7】**
见附件中的 `string/string7.in` 与 `string/string7.ans`。
该组样例满足测试点 $13\sim14$ 和测试点 $16\sim17$ 的约束条件。
**【样例 #8】**
见附件中的 `string/string8.in` 与 `string/string8.ans`。
该组样例满足测试点 $18\sim20$ 的约束条件。
**【数据范围】**
对于所有测试数据，保证：$1\leq n\leq10$，$1\leq |S_i|\leq5\times10^4$，$1\leq |T|,K\leq5\times10^5$，字符串仅包含小写英文字母 $\texttt{a}\sim\texttt{z}$。
| 测试点编号 | $n\leq$ | $\lvert S_i\rvert\leq$ | $\lvert T\rvert\leq$ | $K\leq$ | 特殊性质 |
|:--:|:--:|:--:|:--:|:--:|:--:|
| $1\sim3$ | $10$ | $50$ | $50$ | $50$ | 无 |
| $4\sim6$ | $10$ | $100$ | $300$ | $300$ | 无 |
| $7\sim10$ | $10$ | $1000$ | $5000$ | $5000$ | 无 |
| $11\sim12$ | $10$ | $5\times10^4$ | $5\times10^5$ | $1$ | 无 |
| $13\sim14$ | $10$ | $5\times10^4$ | $5\times10^5$ | $10$ | 无 |
| $15$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 所有字符均为 $\texttt{a}$ |
| $16\sim17$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 所有字符在 $\{\texttt{a},\texttt{b}\}$ 中独立均匀随机生成 |
| $18\sim20$ | $10$ | $5\times10^4$ | $5\times10^5$ | $5\times10^5$ | 无 |