SUBSTRINGS COUNT

SUBSTRINGS COUNT

 Submissions

Attempted by: 497

|

Solved by: 60

|

Partially Solved by: 353

|

---

 

• Algorithms
• Binary Search
• Data Structures
• Hashing
• Medium

  Edit

Problem

Editorial

My Submissions

Analytics

 The Big Bang Challenge

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

(Plaintext Link)

3
code
coder
coding
2
1 3 code
1 3 co

Sample Output

(Plaintext Link)

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

-------------------------------------CODE-----------------------------------------------------------------------------------------------------

GENERATE ALL POSSIBLE SUB STRING OF ALL STRING WHICH CAN BE DONE IN N*45(SINCE LENGTH OF EACH STRING =10 SO 45 SUBSTRINGS IN EACH STRING )

NOW WE  WHENE WE ARE  ADDING ANY INDEX , INCREASE HAS COUNT OF ALL SUBSTRING AT THAT THAT CAN BE FORMED BY STRING AT THAT INDEX (ALL SUBSTRINGS ) ,SIMILARLY FOR DELETE , 

-----------------------------------------------------CODE-----------------------------------------------------------------------------------

#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(lli i=0;i<q;i++)
   printf("%lld\n",result[i]);
   
}