Count Of Substrings

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

Powered By
CHP Adblock Detector Plugin | Codehelppro