C++ STL & Tricks-1

C++ এ কিছু build in লাইব্রেরী আছে, যাদেরকে বলা হয় standard template library. এইসব STL ব্যবহার করে অনেক প্রবলেম অনেক সহজে করে ফেলা যায়। যেমন কোন প্রবলেমে যদি stack,queue এইগুলা ব্যবহার করা লাগে, এইগুলার জন্য নতুন করে কোড লেখার প্রয়োজন পরে না। stack,queue stl ব্যবহার করেই প্রবলেম সল্ভ করা যায়।

vector:

ভেক্টর নরমাল এ্যারের মতই। এর সুবিধা হল যখন ইচ্ছে সাইজ পরিবর্তন করা যায়।

vector declare:

vector ব্যবহার করার জন্য header file vector include করতে হবে।
vector < type > Name;

Code Book

Programming contest লাইফে এখন পর্যন্ত যত Data structure এবং Algorithm শিখেছি তার সকল কালেকশন এই PDF এ পাওয়া যাবে।

 

 

                   ~ Happy coding ~

KMP (Knuth-Morris-Pratt algorithm)

KMP কি?

kmp স্ট্রিং ম্যাচিং এ্যালগরিদম। Kmp লিনিয়ার টাইমে একটা স্ট্রিং T তে একটা প্যাটার্ন স্ট্রিং P কতবার আছে এবং কোন কোন পজিশনে আছে তা বের করে।

KMP কিভাবে কাজ করে?

Kmp কিভাবে কাজ করে তা বুঝার আগে একটা স্ট্রিং T থেকে প্যাটার্ন স্ট্রিং P কতবার ও কোথায় আছে তার naive solution টা দেখে নেয়া জরুরী।

Naive solution:

উপরে solution এ T এর প্রতি পজিশন থেকে P স্ট্রিং ম্যাচ করে দেখা হচ্ছে এবং কোথাও ম্যাচ না পেলে আবার P স্ট্রং এর প্রথম পজিশনে গিয়ে ম্যাচ করে দেখা হচ্ছে।
Kmp এ্যালগরিদম ম্যাচ না পেলে P স্ট্রিং এর বার বার প্রথম পজিশন এ গিয়ে ম্যাচ করানোর জিনিস টা স্কিপ করে।
Kmp এ্যালগরিদমে একটা ফাংশন থাকে যাকে prefix/π/failure ফাংশন বলা হয়ে থাকে।
এই ফাংশন একটা π এ্যারে তৈরী করে দেয়, যাতে প্যাটার্ন স্ট্রিং P এর সব পজিশনে কতটুক প্রিফিক্স ম্যাচ করে তা থাকে।

Python: Graph Theory Algorithm

পাইথনের ডাটা-স্ট্রাকচার ব্যবহার করে কিভাবে গ্রাফ থিওরির এ্যালগরিদম ইমপ্লিমেন্ট করতে হয়, তা দেখানো হয়েছে। এখান থেকে গ্রাফ থিওরি সর্ম্পকে তেমন কিছু জানা যাবে না কিন্তু গ্রাফ থিওরি জানা থাকলে এই কোড গুলা থেকে কিভাবে ইমপ্লিমেন্ট করতে হয় তা ধারনা পাওয়া যাবে।

Python: Sorting Algorithm

আশা করি এই কোড দেখে পাইথনের ডাটাস্ট্রাকচার সর্ম্পকে কিছু ধারনা নেয়া যাবে।

পাইথনের কোড বুঝার আগে মনে রাখার মত কিছু জিনিসঃ