Polycarpus is Looking for Good Substrings

题意翻译

## 题目描述 我们把字符串 $ s[a,b]=s_{a}s_{a+1}...\ s_{b} $ $ (1<=a<=b<=|s|) $ 叫做字符串 $ s=s_{1}s_{2}\dots s_{|s|} $ 的一个子串。其中 $ |s| $ 是字符串 $ s $ 的长度。 一个非空字符串 $ t $ 的字符集是包含了字符串 $t$ 中的字符的集合。比如，字符串 `"aab"` 的字符集是 `{'a','b'}`。 让我们把 $C$ 定义为一个任意字符串 $s$ 的子串的字符集。我们将 $r(C,s)$ 叫做 $s$ 的子串集合中满足字符集为 $C$ 的最大内含的数量。而如果对于由子串组成的集合中某个子串 $ s[a,b] $（设其长度为 $ n=b-a+1 $）, 不存在子串 $ s[x,y] $ 长度大于 $ n $ 且 $ 1\le a\le b\le y\le |s| $，那它是这个集合中的一个最大内含。 $ s $ 的两个子串不管内容是否一样，只要位置不同，就会被认定为是不同的。 Polycarpus 在字符串学课上得到了一个有挑战性且实际的一个任务。他必须要对于给定的字符串 $s$ 和字符集 $C_{1},C_{2},\dots,C_{m}$，算出 $ r(C_{i},s)$ $(i\in[1,m])$。 Polycarpus 不想被大学驱逐而参军，所以请帮助他解决这个问题。 ## 输入格式 第一行是一个非空字符串 $ s $ $ (1<=|s|<=10^{6}) $。 第二行是一个整数 $ m $ $ (1<=m<=10^{4}) $。接下来 $ m $ 行，第 $i$ 行是一个字符串 $ c_{i} $，其字符集是 $ C_{i} $。保证每一行中的 $c_i$ 中字符不重复。 注意 $ C_{i} $ 不一定不相同。所有给定的字符串仅包含英文小写字母。 ## 输出格式 输出 $ m $ 个整数，第 $i$ 个整数等于 $ r(C_{i},s) $。

题目描述

We'll call string $ s[a,b]=s_{a}s_{a+1}...\ s_{b} $ $ (1<=a<=b<=|s|) $ a substring of string $ s=s_{1}s_{2}...\ s_{|s|} $ , where $ |s| $ is the length of string $ s $ . The trace of a non-empty string $ t $ is a set of characters that the string consists of. For example, the trace of string "aab" equals {'a', 'b'}. Let's consider an arbitrary string $ s $ and the set of its substrings with trace equal to $ C $ . We will denote the number of substrings from this set that are maximal by inclusion by $ r(C,s) $ . Substring $ s[a,b] $ of length $ n=b-a+1 $ belonging to some set is called maximal by inclusion, if there is no substring $ s[x,y] $ in this set with length greater than $ n $ , such that $ 1<=x<=a<=b<=y<=|s| $ . Two substrings of string $ s $ are considered different even if they are equal but they are located at different positions of $ s $ . Polycarpus got a challenging practical task on a stringology exam. He must do the following: given string $ s $ and non-empty sets of characters $ C_{1} $ , $ C_{2} $ , $ ... $ , $ C_{m} $ , find $ r(C_{i},s) $ for each set $ C_{i} $ . Help Polycarpus to solve the problem as he really doesn't want to be expelled from the university and go to the army!

输入输出格式

输入格式

The first line contains a non-empty string $ s $ $ (1<=|s|<=10^{6}) $ . The second line contains a single integer $ m $ $ (1<=m<=10^{4}) $ . Next $ m $ lines contain descriptions of sets $ C_{i} $ . The $ i $ -th line contains string $ c_{i} $ such that its trace equals $ C_{i} $ . It is guaranteed that all characters of each string $ c_{i} $ are different. Note that $ C_{i} $ are not necessarily different. All given strings consist of lowercase English letters.

输出格式

Print $ m $ integers — the $ i $ -th integer must equal $ r(C_{i},s) $ .

输入输出样例

输入样例 #1

aaaaa
2
a
a

输出样例 #1

1
1

输入样例 #2

abacaba
3
ac
ba
a

输出样例 #2

1
2
4