CF316G3 Good Substrings

聪明的海狸最近对一个新的单词游戏产生了兴趣。游戏的目标如下：统计某个字符串 $s$ 的不同“好子串”的数量。判断一个字符串是否为“好”的依据是一些规则。总共有 $n$ 条规则。每条规则由三元组 $(p, l, r)$ 描述，其中 $p$ 是一个字符串，$l$ 和 $r$（$l \leq r$）是整数。我们说字符串 $t$ 满足规则 $(p, l, r)$，当且仅当字符串 $t$ 在字符串 $p$ 中出现的次数在 $l$ 到 $r$ 之间（包含 $l$ 和 $r$）。例如，字符串 "ab" 满足规则 ("ab", $1$, $2$) 和 ("aab", $0$, $1$)，但不满足规则 ("cd", $1$, $2$) 和 ("abab", $0$, $1$)。 字符串 $s[l...r]$（$1 \leq l \leq r \leq |s|$）表示字符串 $s = s_1 s_2 \ldots s_{|s|}$ 的子串 $s_l s_{l+1} \ldots s_r$。 字符串 $t$ 在字符串 $p$ 中出现的次数，定义为满足 $p[l...r]=t$ 的整数对 $(l, r)$ 的数量（$1 \leq l \leq r \leq |p|$）。 我们称字符串 $t$ 是“好”的，当且仅当它满足所有 $n$ 条规则。聪明的海狸请你帮他写一个程序，计算字符串 $s$ 中不同的“好子串”的数量。两个子串 $s[x...y]$ 和 $s[z...w]$ 被认为是不同的，当且仅当 $s[x...y] \neq s[z...w]$。

第一行包含字符串 $s$。 第二行包含整数 $n$。 接下来的 $n$ 行，每行包含一个规则，每个规则由一个字符串和两个整数 $p_i, l_i, r_i$ 组成，字符串和整数之间用一个空格分隔（$0 \leq l_i \leq r_i \leq |p_i|$）。保证所有给定的字符串非空且只包含小写英文字母。 对于 30 分的子任务（子任务 G1）： - $0 \leq n \leq 10$。 - 字符串 $s$ 的长度和字符串 $p$ 的最大长度 $\leq 200$。 对于 70 分的子任务（子任务 G1+G2）： - $0 \leq n \leq 10$。 - 字符串 $s$ 的长度和字符串 $p$ 的最大长度 $\leq 2000$。 对于 100 分的子任务（子任务 G1+G2+G3）： - $0 \leq n \leq 10$。 - 字符串 $s$ 的长度和字符串 $p$ 的最大长度 $\leq 50000$。

输出一个整数，表示字符串 $s$ 中“好子串”的数量。

在第一个样例测试中，有三个“好子串”："aab"、"ab" 和 "b"。 在第二个测试中，只有子串 "e" 和 "t" 是“好”的。 由 ChatGPT 4.1 翻译