Codechef – Shift The String

C
Problem NameShift The String
JudgeCodechef
Problem Linkhttps://www.codechef.com/problems/TASHIFT
Algorithms & DSString Hashing, Rabin Karp
#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)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!