HackerEarth Substring Queries problem solution

In this HackerEarth Substring Queries problem solution, we have given a string S, answer Q queries. Each query contains string qstr. Please output the number of substrings of S that contain some anagram of qstr as a subsequence.

HackerEarth Substring Queries problem solution.

`#include <bits/stdc++.h>using namespace std;#define MOD                     1000000007#define pb(x)                   push_back(x)#define mp(x,y)                 make_pair(x,y)#define FF                      first#define SS                      second#define s(n)                    scanf("%d",&n)#define sl(n)                   scanf("%lld",&n)#define sf(n)                   scanf("%lf",&n)#define ss(n)                   scanf("%s",n)#define sc(n)                   {char temp[4]; ss(temp); n=temp[0];}#define INF                     (int)1e9#define LINF                    (long long)1e18#define EPS                     1e-9#define maX(a,b)                ((a)>(b)?(a):(b))#define miN(a,b)                ((a)<(b)?(a):(b))#define abS(x)                  ((x)<0?-(x):(x))typedef long long ll;typedef unsigned long long LL;typedef pair<int,int> PII;typedef pair<LL,LL> PLL;typedef pair<int,PII> TRI;typedef vector<int> VI;typedef vector<LL> VL;typedef vector<ll> vl;typedef vector<PII> VII;typedef vector<TRI> VT;int n;int TEST_NO;char a[100005];int cnt[62];ll ONE = 1;inline int val(char c) {    if(c >= 'a') return 10 + 26 + c - 'a';    if(c >= 'A') return 10 + c - 'A';    else return c - '0';}void precompute() {    }void read() {    ss(a);    n = strlen(a);  }void preprocess() {    }ll find_ans(ll mask) {    int st = 0, en = 0;    ll run = 0;    ll ans = 0;    memset(cnt, 0, sizeof cnt);    while(en < n and st < n) {        int added = val(a[en]);        cnt[added]++;        if(cnt[added] == 1) run |= ONE << added;        while(st < n and ((run & mask) == mask)) {                      ans += n - en;            int sub = val(a[st]);            cnt[sub]--;            if(cnt[sub] == 0) run ^= ONE << sub;            st++;           }        en++;    }    return ans;}void solve() {    int q;    s(q);    while(q--) {        ll mask = 0;        string qstr;        cin >> qstr;        int len = qstr.length();        for (int i = 0; i < len; ++i) {            mask |= ONE << val(qstr[i]);        }        printf("%lld\n", find_ans(mask));    }   }int main() {    precompute();    int t;    s(t);    for(TEST_NO = 1; TEST_NO <= t; TEST_NO ++) {        read();        preprocess();        solve();    }    return 0;}`

Second solution

`#include<bits/stdc++.h>using namespace std;#define vi vector < int >#define pii pair < int , int >#define pb push_back#define mp make_pair#define ff first#define ss second#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )#define ll long long#define llu unsigned long long#define MOD 1000000007#define INF 2000000000#define dbg(x) { cout<< #x << ": " << (x) << endl; }#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }#define all(x) x.begin(),x.end()#define mset(x, v) memset(x, v, sizeof(x))#define si(x) (int)x.size()int ID(char ch){    if('a' <= ch && ch <= 'z')        return ch - 'a';    if('A' <= ch && ch <= 'Z')        return ch - 'A' + 26;    if('0' <= ch && ch <= '9')        return ch - '0' + 52;    assert(0);}ll solve(string s,string q){    int i,j,n = si(s),m = si(q);    int pos[62],f[62];    for(i=0;i<62;i++)    {        pos[i] = -1;        f[i] = 0;    }    vi v;    for(i=0;i<m;i++)    {        f[ID(q[i])] = 1;        v.pb(ID(q[i]));    }    ll ans = 0;    int mx = -1,mid = -1;    int done = 0;    for(i=n-1;i>=0;i--)    {        int id = ID(s[i]);        if(pos[id] == -1 && f[id])            done++;        if(f[id])        {            pos[id] = i;            mx = max(mx,i);            if(i == mx)                mid = id;            if(id == mid)            {                mx = -1;                for(j=0;j<si(v);j++)                {                    int p = v[j];                    mx = max(mx,pos[p]);                    if(mx == pos[p])                        mid = p;                }            }        }        if(done != m)        {            continue;        }        ans += (n-mx);    }    return ans;}int main(){    int t,n,i,q;    scanf("%d",&t);    assert(1 <= t && t <= 3);    while(t--)    {        string s;        cin>>s;        n = si(s);        assert(1 <= n && n <= 100000);        scanf("%d",&q);        assert(1 <= q && q <= 200);        while(q--)        {            string qs;            cin>>qs;            int m = si(qs);            assert(1 <= m && m <= 62);            ll ans = solve(s,qs);            printf("%lld\n",ans);        }    }    return 0;}`