TIMUS - 1517. Freedom of Choice Tutorial
Problem Description here
প্রব্লেমটিতে মূলত n সাইজের দুইটি স্ট্রিং দেয়া থাকবে। দুইটি স্ট্রিং এর মধ্যকার Longest Common Substring টি প্রিন্ট করতে হবে।
সলুশ্যন আইডিয়াঃ
১) বাইনারী সার্চ করে আমরা সর্বোচ্চ কোন Length এর কমন সাবস্ট্রিং সম্ভব বের করে নিবো।
২) নির্দিষ্ট Length এর কমন সাবস্ট্রিং সম্ভব কি না এই কাজটি কীভাবে করবো?
শুরুতে দুইটা স্ট্রিং এর জন্য Prefix Hash বের করে রাখবো।
এরপর, প্রথম স্ট্রিং এর জন্য এই নির্দিষ্ট সাইজের যতোগুলো সাবস্ট্রিং পসিবল তাদের হ্যাশ ভ্যালু ম্যাপে সেইভ রাখবো।
এখন, দ্বিতীয় স্ট্রিং এও যদি এই নির্দিষ্ট সাইজের সাবস্ট্রিং এর জন্য এমন একটি হ্যাশ ভ্যালু পাই যা অলরেডি ম্যাপে আছে তারমানে এই সাইজের কমন সাবস্ট্রিং বানানো সম্ভব।
এই প্রব্লেমে সেটার এমন কিছু টেস্টকেস দিয়েছে যে সিংগেল হ্যাশিং এর ক্ষেত্রে কলিশন হওয়ার সম্ভাবনা অনেক বেশি। এজন্য, ডাবল হ্যাশিং করাই শ্রেয়।
এখন প্রব্লেমটি তোমার নিজে নিজে সলভ এর চেষ্টা করা উচিৎ। এরপরেও না পারলে নিজ দায়িত্বে সলুশ্যন দেখতে পারো।
বিঃদ্রঃ সলুশ্যন দেখে প্রব্লেম সলভ ভালো প্র্যাকটিস না।
Comments
Post a Comment