LightOJ – Substring Frequency

L
Problem NameSubstring Frequency
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/substring-frequency
Algorithms & DSString Hashing, Rabin Karp
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>rHash[4]; ll base[]= {29,31,37,41}; ll mod[]= {1000000007,1000000009,1000000021,1000000033}; ll basePow[4][1000006]; ll hashct=1; void ctBasePow() { for(ll i=0;i<hashct;i++)basePow[i][0]=1; for(ll i=1; i<=1000000; i++) { for(ll j=0; j<hashct; j++) { basePow[j][i]=(basePow[j][i-1]*base[j])%mod[j]; } } } void ctRollHash(string s) { ll len=s.size(); ll ch=s[0]-'a'+1; for(ll i=0; i<hashct; i++){ rHash[i].resize(len+5); rHash[i][0]=ch; } for(ll i=1; i<len; i++) { for(ll j=0; j<hashct; j++) { rHash[j][i]=(((rHash[j][i-1]*base[j])%mod[j])+(s[i]-'a'+1))%mod[j]; } } } vector<ll>pHash; void ctPatHash(string s) { ll len=s.size(); ll ch=s[0]-'a'+1; pHash.resize(hashct+2); for(ll i=0;i<hashct;i++)pHash[i]=ch; for(ll i=1; i<len; i++) { for(ll j=0; j<hashct; j++) { pHash[j]=(((pHash[j]*base[j])%mod[j])+(s[i]-'a'+1))%mod[j]; } } } ll solve(string pt,string s) { ll n=pt.size(); ctRollHash(s); ctPatHash(pt); ll idx=n-1; ll len=s.size(); ll ans=0; for(ll i=idx; i<len; i++) { ll ct=0; for(ll j=0; j<hashct; j++) { ll val=rHash[j][i]; if(i>=n) { val=val-((rHash[j][i-n]*basePow[j][n])%mod[j]); if(val<0)val+=mod[j]; } if(pHash[j]==val)ct++; } if(ct==hashct) { ans++; } } return ans; } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); ctBasePow(); ll t; cin>>t; string pt,s; for(ll T=1;T<=t;T++){ cin>>s; cin>>pt; ll ans=solve(pt,s); cout<<"Case "<<T<<": "; cout<<ans<<"\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 !!