#P18346. Dictionary
Dictionary
Dictionary
题目描述
你打算在接下来的 天里学习一本词典中的单词。词典用一个长度为 、仅由小写英文字母组成的字符串 表示, 的每个非空子串都是一个单词。相同字符串视为同一个单词,即使它在 中出现了多次。
第 天给定两个位置 。你会学习所有以
为前缀的单词。
每天结束后,求从第一天到当前这一天为止,你已经学习了多少个不同的单词。已经学过的单词不会被重复计数。
输入格式
第一行包含一个整数 ,表示测试数据组数。
对于每组测试数据:
第一行包含一个仅由小写英文字母组成的非空字符串 ,其长度为 。
第二行包含一个整数 ,表示学习的天数。
接下来 行,第 行包含两个整数 ,表示第 天学习所有以前缀 开头的单词。
输出格式
对每组测试数据输出一行,包含 个以空格分隔的整数 ,其中 表示从第一天到第 天为止,已经学习的不同单词数量。
数据范围
- ;
- ;
- 仅包含小写英文字母;
- ;
- 一个输入文件内,所有测试数据的 之和不超过 ;
- 一个输入文件内,所有测试数据的 之和不超过 。
样例输入 1
2
abcabd
3
1 3
1 2
6 6
aaa
3
3 3
2 3
1 3
样例输出 1
4 6 7
3 3 3
样例说明
第一组测试数据中:
- 第一天学习了 abc、abca、abcab、abcabd,共 个单词。
- 第二天符合要求的单词为 ab、abc、abca、abcab、abcabd、abd。其中 个已经学过,因此累计学习 个不同单词。
- 第三天学习了此前未学过的 d,累计学习 个不同单词。
第二组测试数据中,第一天就已经学习了 a、aa、aaa,之后的累计数量始终为 。