স্ট্রিং

স্ট্রিং ম্যাচিং: নুথ-মরিসন-প্র্যাট (কেএমপি) অ্যালগরিদম

আজকে আমরা শিখবো কেএমপি (KMP) অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করা। কেএমপি শব্দটি এসেছে ৩জন কম্পিউটার বিজ্ঞানী Donald Knuth, James H. Morris এবং Vaughan Pratt এর নাম থেকে। আমাদের প্রবলেম হলো একটা দুটি স্ট্রিং text এবং pattern দেয়া আছে, আমাদের বলতে হবে text এর ভিতর pattern স্ট্রিংটি সাবস্ট্রিং হিসাবে আছি কিনা। যেমন ধরো টেক্সটটি হলো "MOD", এই স্ট্রিংটার ৬টা সাবস্ট্রিং আছে "M", "O", "D", "MO", "OD" এবং "MOD", এখন যদি pattern = "MO" খুজতে বলে আমরা true রিটার্ন করবো। ব্রুটফোর্স অ্যালগরিদম ব্যবহার করে স্ট্রিং ম্যাচিং করার টাইম কমপ্লেক্সিটি $O(n*m)$, যেখানে $n$ এবং $m$ হলো টেক্সট ও ...
Read More

রবিন-কার্প স্ট্রিং ম্যাচিং

রবিন-কার্প (Rabin-carp) একটি স্ট্রিং ম্যাচিং অ্যালগোরিদম। দুটি স্ট্রিং দেয়া থাকলে এই অ্যালগোরিদমটি বলে দিতে পারে যে ২য় স্ট্রিংটি প্রথম স্ট্রিং এর সাবস্ট্রিং কিনা। রবিন-কার্প রোলিং হ্যাশ টেকনিক ব্যবহার করে স্ট্রিং ম্যাচিং করে। যদিও স্ট্রিং ম্যাচিং এর জন্য কেএমপি অ্যালগোরিদম ব্যবহার করাই ভালো, কিন্তু রবিন-কার্প শেখা গুরুত্বপূর্ণ মূলত রোলিং হ্যাশ কিভাবে কাজ করে সেটা শেখার জন্য। এই লেখাটা পড়ার আগে মডুলার অ্যারিথমেটিক সম্পর্কে জেনে আসতে হবে। স্ট্রিং ম্যাচিং করার সময় প্রথম স্ট্রিং টাকে আমরা বলবো টেক্সট (Text) এবং দ্বিতীয়টিকে প্যাটার্ন (Pattern)। আমাদের কাজ হলো টেক্সট এর মধ্যে প্যাটার্ন...
Read More