SPOJ – NHAY – A Needle in the Haystack

Problem NameNHAY – A Needle in the Haystack
Problem Linkhttps://www.spoj.com/problems/NHAY/
Algorithms & DSString Hashing
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define PB push_back #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); vector<ll>for_hash1; vector<ll>power_p; void pow_p() { ll POWER=1; ll P=31,M=1e9+7; power_p.PB(POWER); for(ll i=1; i<=1000000; i++) { POWER=((POWER%M)*(P%M))%M; power_p.push_back(POWER); } } ll hash1(string S,ll status) { ll P=31,M=1e9+7; ll SIZ=S.size(); ll ANS=0; for(ll i=0; i<SIZ; i++) { ll VAL=(ANS*P)%M; ANS=(((S[i]-'a'+1)%M)+(VAL%M))%M; if(status==0) for_hash1.push_back(ANS); } return ANS; } ll seg_hash(ll l,ll r) { ll P=31,M=1e9+7; ll ans=for_hash1[r]; if(l>0) { ll dif=(r-l)+1; ans-=(for_hash1[l-1]*power_p[dif])%M; ans+=M; ans%=M; } return ans; } int main() { pow_p(); //freopen("1input.txt","r",stdin); fast; ll tcase=1; //cin>>tcase; for(ll test=1; test<=tcase; test++) { ll n; while(cin>>n) { string pattern,s; cin>>pattern>>s; ll siz=s.size(); ll siz_pattern=pattern.size(); if(siz_pattern>siz) { cout<<"\n"; continue; } for_hash1.clear(); ll tm=hash1(s,0); ll hash_value=hash1(pattern,1); ll pos=siz_pattern; vector<ll>ans; for(ll i=pos-1; i<siz; i++) { ll l=i-(siz_pattern-1),r=i; ll val=seg_hash(l,r); string tm=s.substr(l,siz_pattern); if(val==hash_value) { if(tm==pattern) { ans.push_back(l); } } } for(ll i:ans) { cout<<i<<"\n"; } } } return 0; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Notify of
Inline Feedbacks
View all comments

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

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

যোগাযোগ করুন

error: Alert: Content is protected !!