substrings-count-3

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 

SAMPLE INPUT
3
code
coder
coding
2
1 3 code
1 3 co

SAMPLE OUTPUT
2 
3

Explanation

Q1:: code coder coding only two out of 3 strings contain cod as substring
Q2:: code coder coding all the 3 strings contain co as substring

Source: hackerearth | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures


Solutions:
##def bs(temp,i,j,k):
##    if k>=j:
##        return j
##    if k<i:
##        return 0
##    while j-i>1:
##        mid=(i+j)/2
##        if temp[mid]<k:
##            i=mid+1
##        elif temp[mid]>k:
##            j=mid-1
##        else:
##            i=mid
##    if temp[j]==k:
##        return j
##    elif temp[i]==k:
##        return i
##    elif temp[i]>k:
##        return i-1
##    else:
##        return i
def bs(temp,i,j,k):
	if k<=temp[i]:
		return i-1
	while j-i>1:
		mid=(i+j)/2
		if temp[mid]<k:
			i=mid
		elif temp[mid]>k:
			j=mid-1
		else:
			j=mid-1
	if temp[j]<k:
		return j
	if temp[i]<k:
		return i
n=eval(input())
d={}
for i in range(0,n):
	s=input()
	length=len(s)
	check={}
	for j in range(0,length):
		for k in range(j,length+1):
			temp=s[j:k]
			if (temp in check)==False:
				if (temp in d)==False:
					d[temp]=[i]
				else:
					d[temp].append(i)
				check[temp]=True
#print d['pp']
#print "Done!"
q=eval(input())
for i in range(0,q):
	l,r,s=(i for i in input().split())
	l=int(l)-1
	r=int(r)-1
	if (s in d)==False:
		print(0)
	else:
		temp=d[s]
		length=len(temp)
	left=bs(temp,0,length-1,l)
	right=bs(temp,0,length-1,r+1)
	print(right-left)
	#print "--------------------------------------------"