시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 3 | 1 | 1 | 100.000% |
Master Zhu has a string $S [1, \ldots, n]$. This string can contain only the first five lowercase English letters. Another peculiar property of $S$ is that the length of each palindrome substring in $S$ is less than $20$.
For a palindrome string $P [1, \ldots, k]$, its tail is the string $P [\lfloor k / 2 \rfloor + 1, \ldots, k]$. For example, the tail of the string "aba
" is "ba
", and the tail of the string "caac
" is "ac
".
Given $L$, $R$, and a string $T$, Master Zhu wants you to find the number of different palindrome substrings in $S [L, \ldots, R]$ such that $T$ is a prefix of their tails. Here, two substrings are considered different if their starting or ending positions in $S$ differ.
The first line of input contains one integer $C$, the number of test cases ($1 \le C \le 50$).
The first line of each test case contains a string $S$ consisting only of the first five lowercase English letters ($1 \le |S| \le 10^5$, the length of each palindrome substring in $S$ is less than $20$).
The second line contains one integer $q$, the number of queries ($1 \le q \le 10^5$). Each of the next $q$ lines contains two integers $L$ and $R$ and a string $T$ consisting only of the first five lowercase English letters ($1 \le L \le R \le |S|$, $1 \le |T| \le 10$).
For each query, print a single line with a single integer: the number of different palindrome substrings in $S [L, \ldots, R]$ such that $T$ is a prefix of their tails.
1 bceaeeddee 5 5 8 e 3 5 e 1 2 a 5 9 d 5 9 de
3 2 0 4 1