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.

ANSWER

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

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

  lli bck_sz=555;
  
  lli read_int()
  {
 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++)
      printf("%d\n",result[i]);
      
}