Light OJ 1314 / Suffix Array-LCP

/***
 created: 2022-08-10-19.53.51
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

vector<int> sac(string s)
{
    s += '`';
    int n = s.size();
    const int A=28;
    vector<int> p(n), c(n), cnt(max(n, A));
    for (int i = 0; i < n; ++i) cnt[s[i]-'`']++;
    for (int i = 1; i < A; ++i) cnt[i] += cnt[i-1];
    for (int i = n-1; i >=0; --i) p[--cnt[s[i]-'`']] = i;
    int rnk = 1;
    for (int i = 1; i < n; ++i)
    {
        if(s[p[i]] != s[p[i-1]])  rnk++;
        c[p[i]] = rnk-1;
    }

    vector<int> pn(n), cn(n);
    for (int k = 0; (1<<k) < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            pn[i] = p[i] - (1<<k);
            if(pn[i] < 0) pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin()+rnk, 0);
        for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
        for (int i = 1; i < rnk; ++i) cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];

        cn[p[0]]=0;
        rnk = 1;
        for (int i = 1; i < n; ++i)
        {
            int x = p[i]+(1<<k), y = p[i-1]+(1<<k);
            if(x >= n)  x -= n;
            if(y >= n)  y -= n;
            pair<int, int> cur = {c[p[i]], c[x]};
            pair<int, int> prev = {c[p[i-1]], c[y]};
            if(cur != prev) rnk++;
            cn[p[i]] = rnk-1;
        }
        c.swap(cn);
    }

    p.erase(p.begin());
    return p;
}

//kasai's alog :: O(n)

vector<int> LCP(string s, vector<int> p)
{
    int n = s.size();
    vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[p[i]] = i;
    int k = 0;
    vector<int> lcp(n-1);
    for (int i = 0; i < n; ++i)
    {
        if(idx[i]==n-1)
        {
            k = 0;
            continue;
        }
        int j = p[idx[i]+1];
        while(i+k<n and j+k<n and s[i+k]==s[j+k]) k++;
        lcp[idx[i]] = k;
        if(k) k--;
    }
    return lcp;
}


int N_Different_Substrings(const vector<int> &lcp,string b)
{
    int n=b.size();

    int res = n*(n+1)/2;

    for(int i=0; i<lcp.size(); i++)
    {
        res-=lcp[i];
    }

    return res;
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        string a;

        int n,m,i,p,q,l,r,ans=0;

        cin>>a;
        cin>>p>>q;

        n=a.size();

        vector<int>sa =sac(a);

        vector<int>lcp =LCP(a,sa);

        l=1;
        r=n-sa[0];

        l=max(l,p);
        r=min(r,q);

        if(l<=r) ans+=(r-l+1);

        for(i=0; i<n-1; i++)
        {
            l=lcp[i]+1;
            r=n-sa[i+1];

            l=max(l,p);
            r=min(r,q);

            if(l<=r) ans+=(r-l+1);
        }

        cout<<"Case "<<cs<<": "<<ans<<nl;

    }


    get_lost_idiot;
}