Count Of Substrings


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 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];
    string s=a;
    return s;

int main()
    int n;
    map <string, vector<int> > m;
    string s;
    for ( int i = 0; i < n; i++ ) 
        for ( int j = 0; j < (int)s.size(); j++ )
            string s1("");
            for ( int k = j; k < (int)s.size(); k++ ) 

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

    int q;
    while ( q-- )
        int l,r;
        scanf("%d %d",&l,&r);
        l--; r--;
        int ans=0;
        if ( s.empty() )
            ans = r-l+1;
            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;
    return 0;
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.