3756: CF212 - B. Polycarpus is Looking for Good Substrings
[Creator : ]
Description
We'll call string $s[a,b]=s_as_{a+1}...s_b\ (1≤a≤b≤|s|)$ a substring of string $s=s_1s_2...s_|s|$, where $|s|$ is the length of strings.
Thetraceof a non-empty stringtis 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 stringsand 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!
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 stringsand 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!
Input
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 ci 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.
The second line contains a single integer $m\ (1≤m≤10^4)$.
Next $m$ lines contain desc
Note that $C_i$ are not necessarily different. All given strings consist of lowercase English letters.
Output
Print $m$ integers − the $i$-th integer must equal $r(C_i,s)$.
Sample 1 Input
aaaaa
2
a
a
Sample 1 Output
1
1
Sample 2 Input
abacaba
3
ac
ba
a
Sample 2 Output
1
2
4