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.

ANSWER

#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;
}