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$ | 无 |