← 返回题目列表

Codeforces · 316/G3

G3. 好的子串

中文机器翻译题面 查看原题

Smart Beaver 最近对一个新的文字游戏感兴趣。要点如下:统计某个字符串 s 中不同的好子串的数量。为了确定一根绳子是否好,游戏使用规则。总共有n条规则。每个规则由一组三个 (p, l, r) 描述,其中 p 是字符串,l 和 r (l ≤ r) 是整数。如果字符串 t 在字符串 p 中出现的次数介于 l 和 r 之间(包含这两个值),我们就说字符串 t 符合规则 (p, l, r)。例如,字符串“ab”,符合规则(“ab”, 1, 2)和(“aab”, 0, 1),但不符合规则(“cd”, 1, 2)和(“abab”, 0, 1)。

字符串 s = s1s2... s|s| 的子串 s[l... r] (1 ≤ l ≤ r ≤ |s|) (|s| 是 s 的长度)是字符串 slsl + 1... sr。

将字符串 p 中字符串 t 的出现次数视为多对整数 l, r (1 ≤ l ≤ r ≤ |p|),使得 p[l...r] = t。

如果字符串 t 符合所有 n 个规则,我们就说它是好的。聪明的海狸请你帮他写一个程序,可以计算字符串 s 中不同的好子串的数量。两个子串 s[x... y] 和 s[z... w] 被视为不同,当且仅当 s[x... y] ≠ s[z... w]。

输入

第一行包含字符串 s。第二行包含整数n。接下来的 n 行包含规则,每行一个。这些行中的每一行都包含一个字符串和两个整数 pi、li、ri,用单个空格分隔 (0 ≤ li ≤ ri ≤ |pi|)。保证所有给定的字符串非空且仅包含小写英文字母。

得分 30 分的输入限制为(子问题 G1):

- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 200。

得分 70 分的输入限制为(子问题 G1+G2):

- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 2000。

获得 100 分的输入限制为(子问题 G1+G2+G3):

- 0 ≤ n ≤ 10。
- 字符串 s 的长度和字符串 p 的最大长度 ≤ 50000。

输出

打印一个整数——字符串 s 的好子串的数量。

示例

输入 #1

aaab
2
aa 0 0
aab 1 1

输出 #1

3

输入 #2

ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1

输出 #2

2

输入 #3

a
0

输出 #3

1

注意

第一个样本测试中有三个好的子字符串:《aab》、《ab》和《b》。

在第二个测试中,只有子字符串“e”和“t”是好的。