SUBSTRINGS COUNT
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.
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.
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.
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
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
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]);
}
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]);
}
