10314: CF EDU - Suffix Array - Step 3 - A. Substring Search
[Creator : ]
Description
Implement the algorithm that was discussed in the lecture.
Given a string $t$ and $n$ queries, each query is a string $s_i$. For each request you need to determine whether the string $s_i$ occurs as a substring in $t$.
Input
The first line of input contains the string $t\ (1≤|t|≤300,000)$.
The second line contains an integer $n$, the number of queries $(1≤n≤300,000)$.
The following $n$ lines contain one non-empty line $s_i$ each. The sum of the lengths of all strings $s_i$ does not exceed $300,000$.
All strings consist of lowercase English letters.
Output
For each request print "Yes" if the string $s_i$ occurs in $t$, and "No" otherwise.
Sample 1 Input
ababba
3
ba
baba
abba
Sample 1 Output
Yes
No
Yes
Sample 2 Input
codeforces
3
code
forces
math
Sample 2 Output
Yes
Yes
No
Sample 3 Input
a
2
a
a
Sample 3 Output
Yes
Yes