থ্রি ইডিয়টস সিনেমাটা দেখেনি এমন মানুষ খুব কমই আছে হয়তো। সেখানে সাইলেন্সর যখন তার স্পিচ লিখছিলো তখন র‍্যাঞ্চো তাকে অন্যদিকে সরিয়ে তার স্পিচের একটা শব্দকে রিপ্লেস করে অন্য শব্দ বসিয়ে দেয়। সীনটা মনে করলে দেখতে পাবেন সেখানে রিপ্লেস অল অপশনটা ব্যবহার করা হয়েছিল। এখন কিভাবে পুরো ডকুমেন্টের সেই নির্দিষ্ট শব্দ যতগুলো আছে সব খুঁজে বের করে সবগুলোকে একসাথে রিপ্লেস করা হয়েছিল সেটা ভাবার বিষয়।

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

ডিএনএ সিকোয়েন্স প্রধানত চারটা ভিত্তির উপর দাঁড়িয়ে আছে। থাইমিন (T), অ্যাডেনিন (A), সাইটোসিন (C) এবং গুয়ানিন (G)। ধরেন আমাদের কাছে একটা সিকোয়েন্স আছে CATCACAGAGA। এখন যদি আমরা CAG প্যাটার্ন খুঁজতে যাই তাহলে সেটা কিভাবে করতে পারি? একটা কথা বলে রাখি, হিউম্যান জিনোমে ৩০০ কোটি ক্যারেক্টার থাকে। সেখান থেকে কোনো প্যাটার্ন খুঁজে বের করতে একটা এফিশিয়েন্ট অ্যালগরিদম প্রয়োজন হবে।

এসব কাযে মূলত আমরা একটা টেক্সট থেকে নির্দিষ্ট প্যাটার্ন খুঁজে বের করছি। আমাদের প্যাটার্নটা ঐ টেক্সটের কতটা ক্যারেক্টার পরে গিয়ে পাওয়া যাচ্ছে অর্থাৎ কত ঘর শিফট করতে হচ্ছে সেটাই মূলত জানার বিষয়। এই বিষয়টাকেই মূলত বলে String Matching।

এই কাজের জন্য আমাদের দরকার brute force algorithm নামে একটা অ্যালগরিদম। ধরি আমাদের কাঙ্ক্ষিত প্যাটার্ন হলো P = p1p2...pm, এবং টেক্সট হলো T = t1t2...tn। ধরি s সংখ্যক ক্যারেক্টার পরে গিয়ে আমাদের কাঙ্ক্ষিত প্যাটার্নটা পাওয়া যাবে যেখানে ts+1 = p1, ts+2 = p2, ..., ts+m = pm। সকল ভ্যালিড শিফট পাওয়ার জন্য আমাদেরকে s = 0 থেকে s = n - m পর্যন্ত সকল সম্ভাব্য শিফটের মধ্যে এই অ্যালগরিদম রান করতে হবে। নিচের উদাহরণে আপনারা ব্যাপারটা ভালভাবে দেখতে পাবেন।

This image is collected from Discrete Mathematics and its application 8th edition by Mr. Kenneth H. Rosen

এখানে ০ থেকে শুরু করে একঘর করে করে এগিয়ে আমাদের কাঙ্ক্ষিত প্যাটার্নটি পাওয়ার চেষ্টা করেছি। দেখা যাচ্ছে এই অ্যালগরিদম দুইটা ভ্যালিড শিফট পেয়েছে, সেগুলো হলো s=2 এবং s=4। অর্থাৎ ২ এবং ৪ নাম্বার ক্যারেক্টার পরে গিয়ে আমরা আমাদের প্যাটার্নটা পেয়েছি।

এবার এর সুডোকোডটা আমরা দেখি।

procedure string match (n, m: positive integers, m ≤ n, t1, t2,… , tn, p1, p2,… , pm: characters)
    for s := 0 to n − m
        j := 1
        while ( j ≤ m and ts+j = pj)
            j := j + 1
        if j > m then print “s is a valid shift”