TIMUS - 1517. Freedom of Choice Tutorial

Problem Description here

প্রব্লেমটিতে মূলত n সাইজের দুইটি স্ট্রিং দেয়া থাকবে। দুইটি স্ট্রিং এর মধ্যকার Longest Common Substring টি প্রিন্ট করতে হবে। 

সলুশ্যন আইডিয়াঃ 

১) বাইনারী সার্চ করে আমরা সর্বোচ্চ কোন Length এর কমন সাবস্ট্রিং সম্ভব বের করে নিবো। 

২) নির্দিষ্ট Length এর কমন সাবস্ট্রিং সম্ভব কি না এই কাজটি কীভাবে করবো?

শুরুতে দুইটা স্ট্রিং এর জন্য Prefix Hash বের করে রাখবো।

এরপর, প্রথম স্ট্রিং এর জন্য এই নির্দিষ্ট সাইজের যতোগুলো সাবস্ট্রিং পসিবল তাদের হ্যাশ ভ্যালু ম্যাপে সেইভ রাখবো। 

এখন, দ্বিতীয় স্ট্রিং এও যদি এই নির্দিষ্ট সাইজের সাবস্ট্রিং এর জন্য এমন একটি হ্যাশ ভ্যালু পাই যা অলরেডি ম্যাপে আছে তারমানে এই সাইজের কমন সাবস্ট্রিং বানানো সম্ভব। 

এই প্রব্লেমে সেটার এমন কিছু টেস্টকেস দিয়েছে যে সিংগেল হ্যাশিং এর ক্ষেত্রে কলিশন হওয়ার সম্ভাবনা অনেক বেশি। এজন্য, ডাবল হ্যাশিং করাই শ্রেয়। 

এখন প্রব্লেমটি তোমার নিজে নিজে সলভ এর চেষ্টা করা উচিৎ। এরপরেও না পারলে নিজ দায়িত্বে সলুশ্যন দেখতে পারো।

বিঃদ্রঃ সলুশ্যন দেখে প্রব্লেম সলভ ভালো প্র্যাকটিস না।

	#define sz 100009
	const ll p1 = 331;
	const ll p2 = 41;
	const ll m1 = 1000000871;
	const ll m2 = 1000003751;
	pll hash_sum[2][sz]; ///First-Hash for p1 ; Second-Hash for p2; hash_sum[0]-hash value of string-1 ; hash_sum[1]-hash value of string-2
	ll p_pow[2][sz];
	void Power()
	{
	p_pow[0][0] = p_pow[1][0] = 1;
	for(int i=1 ; i<=1e5+5 ; i++){
	p_pow[0][i] = (p_pow[0][i-1] * p1)%m1;
	p_pow[1][i] = (p_pow[1][i-1] * p2)%m2;
	}
	}
	void PrecalHash(string &s , int id , int n)
	{
	hash_sum[id][0] = {0 , 0};
	for(ll i=0 ; i<n ; i++){
	hash_sum[id][i+1].first = (hash_sum[id][i].first + (s[i]-'A'+1)*p_pow[0][i]) % m1;
	hash_sum[id][i+1].second = (hash_sum[id][i].second + (s[i]-'A'+1)*p_pow[1][i]) % m2;
	}
	}
	bool isPossible(int len , int n)
	{
	map<pii , bool>m;
	for(int i=1 ; i<=n-len+1 ; i++){
	int start = i-1;
	int finish = i+len-1;
	int hash1 = (((hash_sum[0][finish].first - hash_sum[0][start].first + m1)%m1)*p_pow[0][100001-start])%m1;
	int hash2 = (((hash_sum[0][finish].second - hash_sum[0][start].second + m2)%m2)*p_pow[1][100001-start])%m2;
	m[make_pair(hash1 , hash2)] = true;
	}
	for(int i=1 ; i<=n-len+1 ; i++){
	int start = i-1;
	int finish = i+len-1;
	int hash1 = (((hash_sum[1][finish].first - hash_sum[1][start].first + m1)%m1)*p_pow[0][100001-start])%m1;
	int hash2 = (((hash_sum[1][finish].second - hash_sum[1][start].second + m2)%m2)*p_pow[1][100001-start])%m2;
	if(m[make_pair(hash1 , hash2)] == true)
	return 1;
	}
	return 0;
	}
	pii DetectnPrint(int len, int n)
	{
	map<pii , int>m;
	int lft=-1,rgt=-1;
	for(int i=1 ; i<=n-len+1 ; i++){
	int start = i-1;
	int finish = i+len-1;
	int hash1 = (((hash_sum[0][finish].first - hash_sum[0][start].first + m1)%m1)*p_pow[0][100001-start])%m1;
	int hash2 = (((hash_sum[0][finish].second - hash_sum[0][start].second + m2)%m2)*p_pow[1][100001-start])%m2;
	m[make_pair(hash1 , hash2)]++;
	}
	for(int i=1 ; i<=n-len+1 ; i++){
	int start = i-1;
	int finish = i+len-1;
	int hash1 = (((hash_sum[1][finish].first - hash_sum[1][start].first + m1)%m1)*p_pow[0][100001-start])%m1;
	int hash2 = (((hash_sum[1][finish].second - hash_sum[1][start].second + m2)%m2)*p_pow[1][100001-start])%m2;
	if(m[make_pair(hash1 , hash2)] > 0){
	lft = start;
	rgt = finish;
	break;
	}
	}
	return make_pair(lft , rgt);
	}
	void Solve(int t)
	{
	int i,j,k,n,start,finish,mxlen=0;
	cin>>n;
	string s1,s2;
	cin>>s1>>s2;
	PrecalHash(s1 , 0 , n);
	PrecalHash(s2 , 1 , n);
	///
	int lo=0,hi=n,mid;
	while(lo <= hi){
	mid = (lo+hi)>>1;
	if(isPossible(mid , n)){
	mxlen = mid;
	lo = mid+1;
	}
	else
	hi = mid-1;
	}
	pii ret = DetectnPrint(mxlen , n);
	if(ret.first==-1 && ret.second==-1)
	cout<<endl;
	else{
	cout<<s2.substr(ret.first , mxlen)<<endl;
	}
	}
	int main()
	{
	CIN;
	Power();
	int t,T;
	T = 1;
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw TIMUS - 1517.cpp hosted with ❤ by GitHub