SUB_PROB - Substring Problem

no tags 

String Matching is an important problem in computer science research and finds applications in Bioinformatics, Data mining,pattern recognition, Internet security and many more areas.

The problem we consider here is a smaller version of it. You are given a string M and N other strings smaller in length than M. You have to find whether each of these N strings is a substring of M. All strings consist of only alphanumeric characters.

You are required to write a C/CPP code to solve the problem.

Input

Input to the program consists of a series of lines. The first line contains the string M (no more than 100000 characters long). The next line contains an integer N (<1000) the number of query strings. Each of the next N lines contain a string S (each of which is no more than 2000 characters long).

Output

Output should consist of N lines each with a character 'Y'/'N' indicating whether the string S is a substring of String M or not.

Example

Input:
abghABCDE
2
abAB

ab


Output:
 
N
Y

Note: The test data for this problem not only consist of the official test cases from the contest,as well some cases of my own.

A testcase is added on 25.7.2010, after rejudging 3 users loose accepted.

 


hide comments
kuszi: 2015-10-10 10:52:59

@tehnar: This is possible however, it will be much safer if your codes will not really on white spaces encoding.

tehnar: 2015-10-10 10:10:27

**** it. End of line in this task is "\r\n" instead of "\n"

I suppose it's because of tests were generated on Windows.
Isn't it possible, when adding new problem to SPOJ, to generate all the tests on server? Or at least run validator to check correctness of tests

Last edit: 2015-10-10 10:46:16
SHASHI BHUSHAN KUMAR: 2015-08-03 12:48:25

nice que

(Tjandra Satria Gunawan)(曾毅昆): 2015-05-25 23:51:10

If you getting WA, try duplicate pattern, I got 4 WAs because of that..
here is one example:
input:
a
2
a
a
output should be:
Y
Y

Martin Radev: 2015-05-05 18:16:13

@Md.shamiul islam The idea of KMP is right, but you have to improve it. For example, say that you have a pattern TONIKA and then another pattern NIKET and the text BARTONIKETA. When searching, you have found TONIK, but the next character is E. Note that NIK which is a suffix of TONIK is a prefix of NIK. => It makes sense to continue with NIKET at E, right?
This is the idea behind Aho-Corasick automation. Read about it ;)

Md.shamiul islam: 2015-05-05 17:47:15

I use KMP but TLE what can i do now

gratitude: 2015-02-13 05:04:11

getting tle using suffix array :(

gratitude: 2015-02-09 23:54:54

Last edit: 2015-02-28 22:18:38
gratitude: 2015-02-01 16:53:52

we should use rabin karp algorithm for better order

parijat bhatt: 2015-01-31 18:15:09

use printf scanf instead of cin & cout


Added by::(){ :|: & };:
Date:2010-07-02
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 C99 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Codefest 2010 CW R#2