NPC2015A - Eefun Guessing Words
Eefun is currently learning to read. His way of learning is unique, by trying to make every possible substring from a given string. However, when the string becomes longer, he can no longer remember all the substring. His friends want to test Eefun's skill by asking questions, given a string S, is there any substring that begins with letter X and ends with letter Y? According to Eefun, each substring contains at least 2 letters. As the given string S is pretty big, Eefun need your help to answer his friend's questions
Input
First line of input contain a single string S which was given by his friends.
Second line contain a number N, the number of questions that Eefun's friends ask.
Next N lines each consists of 2 characters, X and Y
Output
For each questions, output a single string "YA" if the substring exists, or "TIDAK" otherwise
(YA means yes and TIDAK means no in Indonesian)
Example
Input: HALO
4
H O
L O
A O
O L
Output: YA
YA
YA
TIDAK
Constraints:
- 'A' ≤ X,Y ≤ 'Z'
- 1 ≤ |S| ≤ 1.000.000
- 1 ≤ N ≤ 1.000.000
hide comments
zen_tob00:
2024-08-31 16:50:42
if you are using cpp cin and cout for input and output and you still have tle problems... try using scanf and printf (i had this problem) |
|
prakash:
2017-01-11 13:32:36
simple one but time limit is too strict o(q)+o(|s|)+fast i/o got AC
|
|
vengatesh15:
2017-01-10 14:32:46
sImple one AC in 1 go:-) |
|
dwij28:
2016-06-27 14:52:35
My approach is O(N + |S|) and I have checked with all the possible inputs I can think of and it runs fine locally. Cannot see why I am getting a WA.
|
|
Alexey Merejine:
2016-03-31 17:27:31
I have WS on submission 16641335.
|
|
Filip Sollar:
2015-12-04 16:38:56
use faster I/O got tle because of that test case very strong |
|
Bhargav Golla:
2015-10-28 03:35:03
Could you suggest what might be wrong with O(Nlog(|S|)) approach I did in submission 15486818? I am getting TLE, and I think we need at least log |S| time to answer each query. |
|
rahul_verma:
2015-10-19 21:05:18
Give me some more test cases !! |
|
Arianto Wibowo:
2015-10-18 15:12:16
@mehmetin Thanks. Rejudged :) |
|
mehmetin:
2015-10-18 14:24:42
I think the input is broken Last edit: 2015-10-18 14:36:32 |
Added by: | Louis Arianto |
Date: | 2015-10-10 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | NPC Schematics 2015 |