NSUBSTR2 - Substrings II
You are given a string T which consists of 40000 lowercase latin letters at most. You are also given some integers A, B and Q. You have to answer Q queries. For i-th query you are given a string Si and you need to output how many times Si appears in T. Immediately after answering the current query you need to add ((A*ans+B) modulo 26+1)-th lowercase symbol of the English alphabet to the end of T where ans is the answer to this query.
Input
The first line of input contains a string T. The next line consists of three integers Q (1<=Q<=40000), A (0<=A<=27) and B (0<=B<=26). The following Q lines contain Q query strings, Si-2 on i-th line. Input will not exceed 600 kb.
Output
Output Q lines. Output the answer to the i-th query on the i-th line output.
Example
Input:
aaaaa
2 0 0
a
aa
Output:
5
5
hide comments
Santiago Palacio:
2011-08-22 15:07:42
Is it possible to use fscanf with spoj?
|
|
Santiago Zubieta:
2011-08-22 15:07:42
ahahaha if time limit is 6.666 s, why the only person who has solved it shows 50.30? |
|
Siarhei Kulik:
2011-08-22 15:07:42
Time limit isn't strict at all. So if you get TLE - your solutions complexity is not optimal. |
|
V0iD!:
2011-08-22 15:07:42
Always getting TLE when using Java... Can someone try this out in Java and reply?? |
Added by: | Sergey Kulik |
Date: | 2011-04-18 |
Time limit: | 1s |
Source limit: | 44444B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Immagination |