Light OJ - 1114 - Easily Readable Tutorial

Problem Description here

প্রব্লেমটিতে মূলত বলা হয়েছে, একটা ডিকশনারি দেয়া থাকবে যেখানে n টি শব্দ থাকবে। প্রতিটি শব্দের ১ম এবং শেষ ক্যারেক্টার ছাড়া বাকি ক্যারেক্টার গুলো যেভাবে ইচ্ছা সাজানো যায়।

এরপর একটি বাক্য দেয়া থাকবে। এই বাক্যের শব্দগুলোও একইভাবে সাজানো যায়। বলতে হবে ডিকশনারি থেকে শব্দ নিয়ে ব্যাকটি কতভাবে গঠন করা যায়? 

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

১) প্রতিটি শব্দ ডিকশনারী তথা ট্রাই তে ইনসার্ট করার সময়ই ঐ শব্দের ২য় থেকে সর্বশেষ ক্যারেক্টার এর আগ পর্যন্ত সর্ট করে নিবো লেক্সিকোগ্রাফিক্যালি। এবং ট্রাই তে প্রতিটি নোডে কতটা স্ট্রিং শেষ হয়েছে সেটা ক্যালকুলেট করে রাখবো। 

২) এরপর, বাক্যের প্রতিটি শব্দও একইভাবে সর্ট করবো এবং দেখবো ডিকশনারী তে এই শব্দটি কতবার ইনসার্ট আছে। প্রতিটি শব্দের ফ্রিকুয়েন্সী গুণ করে গুণফলই হবে এন্সার। 

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

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

	const int N = 1e5+9;
	int tot_node = 1;
	int to[N][62] , endmark[N];
	void Add(char *s)
	{
	int sz = strlen(s) , curr = 1; ///curr - Root node
	if(sz > 2)
	sort(s+1 , s+sz-1);
	for(int i=0 ; i<sz ; i++){
	int ch = s[i]-'A';
	if(!to[curr][ch]) to[curr][ch] = ++tot_node;
	curr = to[curr][ch];
	}
	endmark[curr]++;
	}
	int Search(string &s)
	{
	int sz = s.size() , curr = 1;
	if(sz > 2)
	sort(s.begin()+1 , s.begin()+sz-1);
	for(int i=0 ; i<sz ; i++){
	int ch = s[i]-'A';
	if(!to[curr][ch]) return 0;
	curr = to[curr][ch];
	}
	return endmark[curr];
	}
	void Clean(int n)
	{
	for(int i=0 ; i<=n ; i++){
	endmark[i] = 0;
	for(int j=0 ; j<=60 ; j++)
	to[i][j] = 0;
	}
	}
	void Solve(int t)
	{
	int i,j,k,n,ans=1,q,sz;
	string s1,s2;
	char str[100005];
	tot_node = 1;
	scin(n);
	for(i=1 ; i<=n ; i++){
	sc("%s",str);
	Add(str);
	}
	scin(q);
	pf("Case %d:\n",t);
	getchar();
	for(i=1 ; i<=q ; i++){
	ans = 1;
	stringstream ss;
	getline(cin , s1);
	ss<<s1;
	while(ss>>s2){
	int ret = Search(s2);
	ans *= ret;
	}
	cout<<ans<<endl;
	}
	Clean(1e5+2);
	}
	int main()
	{
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1114.cpp hosted with ❤ by GitHub