235C - Cyclical Quest - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ll long long int
#define fi first
#define se second
 
#define md1 1000000007
#define md2 998244353 //r=3  upto root of 1<<23
#define md3 1000000009
#define md4 7340033   //r=5  upto root of 1<<20

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
using namespace __gnu_pbds;
using namespace std;

// ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

struct Vertex{
    int nxt[26];
    int link=-1,len=0,cnt=0;
    Vertex(){
        for(int i=0;i<26;i++)nxt[i]=-1;
    }
};
Vertex Vtx[2000006];
int q,last,sz;
string s,str;
vector<int> Len[1000006];
void build_sa(char ch){
    int c=ch-'a';
    int curr=++sz;
    Vtx[curr].len=Vtx[last].len+1;
    int p=last;
    while(p!=-1&&Vtx[p].nxt[c]==-1){
        Vtx[p].nxt[c]=curr;
        p=Vtx[p].link;
    }
    if(p==-1)Vtx[curr].link=0;
    else{
        int q=Vtx[p].nxt[c];
        if(Vtx[q].len==Vtx[p].len+1)Vtx[curr].link=q;
        else{
            int clone=++sz;
            Vtx[clone].len=Vtx[p].len+1;
            Vtx[clone].link=Vtx[q].link;
            for(int i=0;i<26;i++)Vtx[clone].nxt[i]=Vtx[q].nxt[i];
            while(p!=-1&&Vtx[p].nxt[c]==q){
                Vtx[p].nxt[c]=clone;
                p=Vtx[p].link;
            }
            Vtx[curr].link=Vtx[q].link=clone;
            Len[Vtx[clone].len].pb(clone);
        }
    }
    Vtx[curr].cnt=1;
    last=curr;
    Len[Vtx[curr].len].pb(curr);
}
vector<int> KMP(string Z){
    vector<int> pi(Z.length());
    pi[0]=0;
    for(int i=1;i<Z.length();i++){
        int j=pi[i-1];
        while(j>0&&Z[i]!=Z[j])j=pi[j-1];
        if(Z[i]==Z[j])j++;

        pi[i]=j;
    }
    return pi;
}
int main(){
    cin>>s;
    for(int i=0;i<s.length();i++){
        build_sa(s[i]);
        // cout<<sz<<"\n";
    }
    for(int i=1000000;i>=1;i--){
        for(int v:Len[i])Vtx[Vtx[v].link].cnt+=Vtx[v].cnt;
    }
    // cout<<sz<<"\n";
    cin>>q;
    while(q--){
        string ogstr;
        cin>>str;int L=str.length();ogstr=str;
        for(int i=0;i<L-1;i++)str+=str[i];
        string currstr="";
        vector<int> pi=KMP(str);
        for(int i=0;i<str.length();i++){
            if(pi[i]==L){
                str=currstr;break;
            }
            currstr+=str[i];
        }
        // cout<<str<<"\n";
        int v=0,ans=0,currLen=0;
        for(int i=0;i<str.length();i++){
            while(v!=-1&&Vtx[v].nxt[str[i]-'a']==-1){
                v=Vtx[v].link;
                currLen=Vtx[v].len;
            }
            if(v==-1)break;
            v=Vtx[v].nxt[str[i]-'a'];
            currLen++;
            
            while(Vtx[v].link!=-1&&Vtx[Vtx[v].link].len>=L){
                v=Vtx[v].link;
                currLen=Vtx[v].len;
            }
            // cout<<v<<" ";
            if(currLen>=L){
                ans+=Vtx[v].cnt;
                // cout<<Vtx[v].cnt<<" ";
            }
            // cout<<"\n";
        }
        cout<<ans<<"\n";
    }
    return 0;
}

// https://codeforces.com/problemset/problem/235/C