# Count Of Substrings

QUESTION

Ria has excellent skills in programming.To boost her intelligence,her class teacher gave her a problem to Count the no:of substrings.\n\nProblem :\nHer Class teacher gave her 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 her teacher wants to know how many strings numbered from L to R contains str as a substrings.\n\nAs expected, Ria solved this problem. What might be her code?\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;
string getstr()
{
char a[11];
scanf("%s",a);
string s=a;
return s;
}

int main()
{
int n;
scanf("%d",&n);
map <string, vector<int> > m;
string s;
for ( int i = 0; i < n; i++ )
{
s=getstr();
for ( int j = 0; j < (int)s.size(); j++ )
{
string s1("");
for ( int k = j; k < (int)s.size(); k++ )
{
s1.push_back(s[k]);
m[s1].push_back(i);
}
}
}

for(map <string, vector<int> >::iterator it = m.begin(); it != m.end(); ++it)
{
vector<int>::iterator sz = unique((it->second).begin(),(it->second).end());
(it->second).resize(distance((it->second).begin(),sz));
}

int q;
scanf("%d",&q);
while ( q-- )
{
int l,r;
scanf("%d %d",&l,&r);
s=getstr();
l--; r--;
int ans=0;
if ( s.empty() )
ans = r-l+1;
else
{
int idx2 = upper_bound(m[s].begin(),m[s].end(),r) - m[s].begin();
int idx1 = lower_bound(m[s].begin(),m[s].end(),l) - m[s].begin();
ans = idx2-idx1;
}
printf("%d\n",ans);
}
return 0;
}``````