3419: CF316 - G3. Good Substrings
[Creator : ]
Description
Smart Beaver recently got interested in a new word game. The point is as follows: count the number of distinct good substrings of some strings. To determine if a string is good or not the game uses rules. Overall there arenrules. Each rule is described by a group of three $(p,l,r)$, where $p$ is a string and $l$ and $r\ (l≤r)$ are integers. We’ll say that string $t$ complies with rule $(p,l,r)$, if the number of occurrences of string $t$ in string $p$ lies between $l$ and $r$, inclusive.
For example, string "ab", complies with rules ("ab",1,2) and ("aab",0,1), but does not comply with rules ("cd",1,2) and ("abab",0,1).
For example, string "ab", complies with rules ("ab",1,2) and ("aab",0,1), but does not comply with rules ("cd",1,2) and ("abab",0,1).
A substring $s[l...r]\ (1≤l≤r≤|s|)$ of string $s=s_1s_2...s_{|s|}\ (|s|$ is a length of $s$) is string $s_ls_{l+1}...s_r$.
Consider anumber of occurrences of string $t$ in string $p$ as a number of pairs of integers $l,r\ (1≤l≤r≤|p|)$ such that $p[l...r]=t$.
We’ll say that stringtis good if it complies with allnrules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of strings. Two substrings $s[x...y]$ and $s[z...w]$ are cosidered to be distinct iff $s[x...y]≠s[z...w]$.
Consider anumber of occurrences of string $t$ in string $p$ as a number of pairs of integers $l,r\ (1≤l≤r≤|p|)$ such that $p[l...r]=t$.
We’ll say that stringtis good if it complies with allnrules. Smart Beaver asks you to help him to write a program that can calculate the number of distinct good substrings of strings. Two substrings $s[x...y]$ and $s[z...w]$ are cosidered to be distinct iff $s[x...y]≠s[z...w]$.
Input
The first line contains string $s$.
The second line contains integer $n$.
Next $n$ lines contain the rules, one per line. Each of these lines contains a string and two integers $p_i,l_i,r_i$, separated by single spaces $(0≤l_i≤r_i≤|p_i|)$. It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.
The input limits for scoring 30 points are (subproblem G1):
The second line contains integer $n$.
Next $n$ lines contain the rules, one per line. Each of these lines contains a string and two integers $p_i,l_i,r_i$, separated by single spaces $(0≤l_i≤r_i≤|p_i|)$. It is guaranteed that all the given strings are non-empty and only contain lowercase English letters.
The input limits for scoring 30 points are (subproblem G1):
- 0≤n≤10.
- The length of string s and the maximum length of string p is ≤200.
- 0≤n≤10.
- The length of string s and the maximum length of string p is ≤2000.
- 0≤n≤10.
- The length of string s and the maximum length of string p is ≤50000.
Output
Print a single integer − the number of good substrings of string $s$.
Sample 1 Input
aaab
2
aa 0 0
aab 1 1
Sample 1 Output
3
There are three good substrings in the first sample test: «aab», «ab» and «b».
Sample 2 Input
ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1
Sample 2 Output
2
only substrings «e» and «t» are good.
Sample 3 Input
a
0
Sample 3 Output
1