DSA Level 3 Competitive Text Processing Suffix Tree - Dictionary Queries

Suffix Tree - Dictionary Queries

hard

Text Processing

Question Solve Solutions

You are given a string S, and Q queries.
Each query consist of a string T.
You have to determine if T is a substring of S.

Input Format

Input consist of A string S and an integer Q followed by Q strings

Output Format

If T is a substring of S, print "y", else print "n"

Constraints

|S| &lt;= 10^5
Q &lt;= 1000
|T| &lt;= 1000

Example

Input

2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz

Output

y
n
y

Suffix Tree - Application 3 - Longest Common Substring

Aho Corasick - Application

Related Questions

easy Shortest Palindrome medium Longest Palindromic Substring hard Kmp Pattern Searching hard Z Algorithm For Pattern Searching hard Find String Roots hard Manacher's Algorithm hard String Rotation hard Prefix And Suffix Count medium Say No To Palindrome medium String Polynomial Hashing medium Diane medium Rabin Karp Pattern Find (spoj) hard Password medium Good Substrings hard Longest Duplicate Substring medium Longest Prefix Suffix