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("%lldn", 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("%lldn",ans);
        }
    }
    return 0;
}

coding problems