VOTAS - Votka and String
Votka loves string very much. Recently he learned prefixes and suffixes. A prefix of a string S is any leading contiguous part of S and a suffix of string S is any trailing contiguous part of S, e.g., the prefixes of string “abc” are { “a”, “ab”, “abc” } and the suffixes are { “abc”, “bc”, “c” }. Votka considers a suffix Si of string S beautiful, if Si has at least b prefixes which are also prefixes of S.
Formally,
let, P = the set of prefixes of the string S
Pi = the set of prefixes of the suffix Si
Then, Si is a beautiful suffix if |P ∩ Pi| ≥ b.
For example, consider S = “abcabcd” and b = 3, then suffix S3 i.e. “abcd” is a beautiful suffix because it has 3 (≥ b) prefixes { “a”, “ab”, “abc” } which are also prefixes of S. Note that, S itself is a beautiful suffix for all b ≤ |S|.
Now Votka thinks about a problem. The problem is, you are given a string S and m numbers {K1, K2, … , Km }. For each number Ki, you have to find the number of beautiful suffixes of S considering b = Ki.
Votka announces that he will give a treat to the first solver of this problem. Luffy, a close friend of Votka, wants to have that treat. As Luffy is very dumb, he asks for your help. Can you help him? :)
Input
Input starts with an integer T (≤ 10), denoting the number of test cases. The first line of each case contains a string S (1 ≤ |S| ≤ 100000). S contains only lowercase English letters. The next line contains an integer m (1 ≤ m ≤ 100000). The following line contains m space separated integers K1, K2, … , Km (0 ≤ Ki ≤ 100000).
Output
For each test case, print m space separated integers (number of beautiful suffixes of S considering b = Ki) in a single line. (Caution: Dataset is large. Use faster I/O. )
Sample
Input: 2 abcabcd 3 3 7 8 aaaaa 5 1 2 3 4 5 Output: 2 1 0 5 4 3 2 1
hide comments
rising_stark:
2024-08-13 20:19:45
Bad question. Time limit is too strict for suffix array nlogn + segment tree to pass. Needs z-function only to pass. |
Added by: | Rofi |
Date: | 2016-07-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |