Codechef – Shift The String

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr ll MX=1000000;
constexpr ll base=29;
constexpr ll mod=1000000007;

vector<ll>basePow;
void ctPow()
{
    basePow.resize(MX+5);
    basePow[0]=1;
    for(ll i=1;i<=MX;i++)basePow[i]=(basePow[i-1]*base)%mod;
}

vector<ll>aHash,bHash;
void ctHash(string a,string b)
{
    ll lena=a.size();
    b+=b;
    ll lenb=b.size();
    aHash.resize(lena+5);
    bHash.resize(lenb+5);
    aHash[0]=a[0]-'a'+1;
    bHash[0]=b[0]-'a'+1;
    for(ll i=1;i<lena;i++)aHash[i]=((aHash[i-1]*base)+(a[i]-'a'+1))%mod;
    for(ll i=1;i<lenb;i++)bHash[i]=((bHash[i-1]*base)+(b[i]-'a'+1))%mod;
}

int main()
{
    ctPow();
    ll n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    ctHash(a,b);
    ll ck=0;
    ll ans[n+5];
    ll idx=0;
    for(ll i=0;i<=n;i++)ans[i]=-1;
    for(ll i=0;i<n;i++){
        for(ll j=max(idx,i);j<(2*n);j++){
            ll sz=i+1;
            ll pre=aHash[i];
            ll val=bHash[j];
            if(j-sz>=0)val-=((bHash[j-sz]*basePow[sz])%mod);
            if(val<0)val+=mod;
            if(pre==val){
                ans[i]=(j-sz+1);
                idx=j;
                break;
            }
        }
        if(ans[i]==-1)break;
    }
    ll ok=-1;
    for(ll i=n-1;i>=0;i--){
        if(ans[i]!=-1){
            ok=ans[i];
            break;
        }
    }
    if(ok==-1)ok=0;
    cout<<ok<<"\n";
    return 0;
}
Code language: PHP (php)