# SUBSTRINGS COUNT

QUESTION

Jack is the most intelligent student in the class.To boost his intelligence,his class teacher gave him a problem named \”Substring Count\”.\n\nProblem :\nHis 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.\n\nEach 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.\n\nAs 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.\n\nINPUT\nFirst 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.\n\nOUTPUT\nprint the correct answer for each of the question asked by his teacher.\n\nCONSTRAINTS\n1<=n<=10000\n1<=strlen(str)<=10\n1<=Q<=5*10^5\n1<=L,R<=n\n\nNOTE: strings consist of only lower case characters.

``````#include<bits/stdc++.h>
using namespace std;
//map<map<string,int> > ma;
string ss;
typedef int lli;
int result;
vector<string>v;
struct node
{
lli x,y,index;
string str;

} qry;

map<string,int> has;
long long int ans=0;

lli bck_sz=555;

{
char r;
bool start=false,neg=false;
lli ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}

bool compare(node a,node b)
{
lli i,j;
i=a.x/bck_sz;
j=b.x/bck_sz;
if(i==j)
{
if(a.y<b.y)
return 1;
else
return 0;
}
else{
if(i<j)
return 1;
else
return 0;
}
}

int join(int index)
{
int l=v[index].size();
for(int i=0;i<l;i++)
has[v[index][i]]++;
}

int del(int index)
{
int l=v[index].size();
for(int i=0;i<l;i++)
has[v[index][i]]--;
}

int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string s;
cin>>ss[i];
int len=ss[i].length();
map<string,int> mp;
for(int k=0;k<len;k++)
{
string p;

for(int j=k;j<len;j++)
{
p+=ss[i][j];
if(!mp[p])
v[i].push_back(p);
mp[p]++;

}
}
mp.clear();

}

int q;
cin>>q;
for(int i=0;i<q;i++)
{
int a,b;
string s;
cin>>a>>b;
cin>>s;
qry[i].x=a-1;
qry[i].y=b-1;
qry[i].index=i;
qry[i].str=s;

}
sort(qry,qry+q,compare);

int  r=-1;
int  l=0;
for(int  i=0;i<q;i++)
{
int  x=qry[i].x;
int  y=qry[i].y;
int  index=qry[i].index;
string s=qry[i].str;
// cout<<" query in the range "<<x<<" "<<y<<endl;

while(r<y)
{

r++;

join(r);
}

while(l>x)
{
l--;
join(l);
}
while(l<x)
{
del(l);
l++;
}
while(r>y)
{
del(r);
r--;
}

result[index]=has[s];

}

for(int i=0;i<q;i++)
cout<<result[i]<<endl;

}
`````` 