UVA 12613 / Suffix Array

/***
 created: 2022-07-07-16.36.57
***/

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

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

    ll 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,b;

        ll n,m,i,j,k,l,s2,s3;

        cin>>a>>k;

        cout<<"Case "<<cs<<": ";


        set<ll>x;

        for(i=0;a[i];i++)
        {
            x.insert(a[i]);
        }


        if(a.size()==x.size())
        {
            n=a.size();

            l=n*((n*k)-n) + (n*(n+1))/2;

            cout<<l<<nl;

            continue;
        }


        b=a;

        b+=a;

        vector<int>sa =sac(b);

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

        s2=N_Different_Substrings(lcp,b);


        if(k-2==0)
        {

//            for(auto i:sa) cout<<i<<" ";
//            cout<<nl;
//            for(auto i:lcp) cout<<i<<" ";
//            cout<<nl;

            cout<<s2<<nl;
            continue;
        }


        b=a;

        b+=a;
        b+=a;


        sa.clear();
        lcp.clear();

        sa =sac(b);

        lcp =LCP(b,sa);

        s3=N_Different_Substrings(lcp,b);

        cout<<(s3-s2)*(k-2) + s2<<nl;

    }


    get_lost_idiot;
}