SUBSTRINGS COUNT
Practice
5 (10 votes)
Binary search algorithm
Medium
Hash function
Data structures
Algorithms
Hash table
Open
Approved
Problem
63% Success 3704 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

Jack is the most intelligent student in the class.To boost his intelligence,his class teacher gave him a problem named "Substring Count".

Problem :
His Class teacher gave him n strings numbered from 1 to n which consists of only lowercase letters (each having length not more than 10) and then ask Q questions related to the given strings.

Each question is described by the 2 integers L,R and a string str,Now his teacher wants to know how many strings numbered from L to R contains str as a substrings.

As expected, Jack solved this problem with in a minute but he failed to solve it efficiently.Now ,its your turn to teach him.How to do it efficiently?? and save him from punishment.

INPUT
First line of input contains a single integer n denoting the number of strings given by class teacher to jack.Next n lines of input contains n strings (one per line).Next line fo input contains a single integer Q denoting the number of questions asked by his teacher.next Q lines of input contains Q question (one per line) as explained above.

OUTPUT
print the correct answer for each of the question asked by his teacher.

CONSTRAINTS
1<=n<=10000
1<=strlen(str)<=10
1<=Q<=5*10^5
1<=L,R<=n

NOTE: strings consist of only lower case characters

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
129 votes
Tags:
MediumOpenApprovedHash tableHash function