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' or '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 test case was added on 25.7.2010, after rejudging 3 users lose accepted.


hide comments
miloy23: 2024-02-21 20:57:28

how to solve this using hashing ?

abcxyz1234: 2022-11-21 05:11:16

nice aho problem

muhammedalajam: 2022-10-02 02:10:45

<snip>
why my solution is getting a runtime error?
[Simes]: use the forum for this.

Last edit: 2022-10-02 06:34:44
noobmaster_39: 2022-09-22 16:33:49

I have Used Double Hashing and got TLE .
Is any optimization possible in this case ?

albatroz: 2022-06-08 01:56:52

TL is not nice

nikito3301: 2022-04-14 07:20:33

KMP also TLE.

jmarcoslima: 2022-02-09 19:32:38

What a dumb time limit

legit_123: 2021-10-13 15:01:10

Add java support!!

mahbubkuet08: 2021-10-10 19:07:09

Did anyone able to solve using robin_karp. I got TLE

jdmoyle: 2021-08-02 20:53:31

Rabin Karp shows TLE at 8


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 NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Codefest 2010 CW R#2