Regular Expressions (রেগুলার এক্সপ্রেশন)

রেগুলার এক্সপ্রেশন (Regular Expressions, বা regex) হলো একটি শক্তিশালী প্যাটার্ন ম্যাচিং টুল যা টেক্সট স্ট্রিংয়ে নির্দিষ্ট প্যাটার্ন খোঁজার এবং সেগুলোর সাথে কাজ করার জন্য ব্যবহৃত হয়। C++11 থেকে, C++ স্ট্যান্ডার্ড লাইব্রেরি <regex> হেডার ফাইলের মাধ্যমে রেগুলার এক্সপ্রেশন সমর্থন করে। এটি আপনাকে স্ট্রিংয়ের মধ্যে প্যাটার্ন খুঁজে বের করা, স্ট্রিং ম্যানিপুলেশন, এবং টেক্সটের মধ্যে বিভিন্ন ম্যানিপুলেশন কাজ সম্পন্ন করতে সহায়তা করে।

রেগুলার এক্সপ্রেশন কী?

রেগুলার এক্সপ্রেশন (regex) একটি টেক্সট ম্যানিপুলেশন ভাষা যা নির্দিষ্ট প্যাটার্নের জন্য টেক্সট অনুসন্ধান, ম্যাচিং এবং প্রতিস্থাপন (search, match, replace) করতে ব্যবহৃত হয়। এটি নিয়মিত প্যাটার্নের আকারে টেক্সটের কোনো অংশে খোঁজা চালায় এবং সেই অনুযায়ী একটি কাজ (যেমন স্ট্রিং প্রতিস্থাপন, স্ট্রিং বিচ্ছেদ) সম্পাদন করে।

রেগুলার এক্সপ্রেশন ব্যবহারের জন্য প্রধান উপাদানগুলি

1. লিটারেল ক্যারেক্টার:
   • সাধারণ টেক্সট মেলানোর জন্য।
2. মেটাচর কিল (Metacharacters):
   • . (Dot): যেকোনো একক ক্যারেক্টারের সাথে মেলে।
   • ^ (Caret): স্ট্রিংয়ের শুরুর সাথে মেলে।
   • $ (Dollar Sign): স্ট্রিংয়ের শেষে মেলে।
   • * (Asterisk): পূর্ববর্তী ক্যারেক্টারটি শূন্য বা একাধিকবার উপস্থিত হতে পারে।
   • + (Plus): পূর্ববর্তী ক্যারেক্টারটি এক বা একাধিকবার উপস্থিত হতে পারে।
   • ? (Question Mark): পূর্ববর্তী ক্যারেক্টারটি শূন্য বা একবার উপস্থিত হতে পারে।
   • [] (Square Brackets): একটি নির্দিষ্ট সেটের মধ্যে যেকোনো একটি ক্যারেক্টারের সাথে মেলে।
   • {} (Curly Braces): নির্দিষ্ট পরিমাণ বর্ণনা করে (যেমন {3} মানে ঠিক ৩টি ক্যারেক্টার)।
   • | (Pipe): অথবা (OR) অপারেটর, যে দুটি প্যাটার্নের মধ্যে যেকোনো একটিতে ম্যাচ হবে।
3. গ্রুপিং এবং ক্যাপচারিং:
   • () (Parentheses): একাধিক ক্যারেক্টার বা প্যাটার্নের গ্রুপিং তৈরি করে।
4. এস্কেপ সিকুয়েন্স:
   • \: একটি বিশেষ ক্যারেক্টারকে এস্কেপ করার জন্য ব্যবহৃত হয়। যেমন, \d ডিজিটের জন্য, \w অক্ষরের জন্য।

C++ এ রেগুলার এক্সপ্রেশন ব্যবহারের উদাহরণ

C++ তে রেগুলার এক্সপ্রেশন ব্যবহারের জন্য <regex> হেডার ফাইলটি ইনক্লুড করতে হয় এবং std::regex ক্লাস ব্যবহার করতে হয়।

১. সাধারণ মেলানো (Matching a Simple Pattern)

#include <iostream>
#include <regex>

int main() {
    std::string text = "I have 100 apples.";
    std::regex pattern("\\d+");  // রেগুলার এক্সপ্রেশন যা সংখ্যা খোঁজে

    // match function ব্যবহার করা
    if (std::regex_search(text, pattern)) {
        std::cout << "Number found!" << std::endl;
    } else {
        std::cout << "No number found." << std::endl;
    }

    return 0;
}

ব্যাখ্যা:

• \\d+: \\d মানে একটি ডিজিট, এবং + মানে এক বা একাধিক ডিজিট।
• std::regex_search(): এটি একটি স্ট্রিংয়ের মধ্যে প্যাটার্ন খুঁজে এবং ফলাফল প্রদান করে।

২. স্ট্রিং প্রতিস্থাপন (Replacing a Pattern)

#include <iostream>
#include <regex>

int main() {
    std::string text = "I have 100 apples and 200 oranges.";
    std::regex pattern("\\d+");  // সব ডিজিটের জন্য রেগুলার এক্সপ্রেশন

    // std::regex_replace ব্যবহার করে প্রতিস্থাপন
    std::string replaced = std::regex_replace(text, pattern, "#");

    std::cout << "Replaced Text: " << replaced << std::endl;

    return 0;
}

ব্যাখ্যা:

• std::regex_replace(): এটি নির্দিষ্ট প্যাটার্নগুলোর সাথে মিলিত অংশগুলিকে একটি নতুন স্ট্রিং দ্বারা প্রতিস্থাপন করে।

৩. বিভিন্ন প্যাটার্ন খোঁজা (Finding Multiple Matches)

#include <iostream>
#include <regex>
#include <vector>

int main() {
    std::string text = "John's phone number is 123-456-7890 and Sarah's is 987-654-3210.";
    std::regex pattern("\\d{3}-\\d{3}-\\d{4}");  // ফোন নম্বরের জন্য প্যাটার্ন

    // std::sregex_iterator ব্যবহার করে সব ম্যাচ খোঁজা
    std::sregex_iterator it(text.begin(), text.end(), pattern);
    std::sregex_iterator end;

    while (it != end) {
        std::cout << "Phone Number: " << it->str() << std::endl;
        ++it;
    }

    return 0;
}

ব্যাখ্যা:

• std::sregex_iterator: এটি রেগুলার এক্সপ্রেশনের সাথে স্ট্রিংয়ের সব মেলে এমন অংশগুলোর উপর ইটরেটর তৈরি করে।

৪. রেগুলার এক্সপ্রেশন কনস্ট্রেনিং (Restricting Pattern Match)

#include <iostream>
#include <regex>

int main() {
    std::string email = "example@domain.com";
    std::regex email_pattern("[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}");

    if (std::regex_match(email, email_pattern)) {
        std::cout << "Valid email address." << std::endl;
    } else {
        std::cout << "Invalid email address." << std::endl;
    }

    return 0;
}

ব্যাখ্যা:

• std::regex_match(): এটি স্ট্রিংটি পুরোপুরি প্যাটার্নের সাথে মেলে কিনা তা পরীক্ষা করে।
• [a-zA-Z0-9._%+-]: এটা একটি সাধারণ ইমেইল প্যাটার্ন।

রেগুলার এক্সপ্রেশন এর সুবিধা

• শক্তিশালী প্যাটার্ন ম্যাচিং: রেগুলার এক্সপ্রেশন আপনাকে স্ট্রিংগুলির মধ্যে খুবই জটিল প্যাটার্ন খুঁজে বের করার সুযোগ দেয়।
• ফ্লেক্সিবিলিটি: আপনি বিভিন্ন ধরনের স্ট্রিং ম্যানিপুলেশন কাজ যেমন, টেক্সট খোঁজা, প্রতিস্থাপন এবং বিভক্ত করতে পারেন।
• কোড সংক্ষিপ্তকরণ: এটি কমপ্লেক্স স্ট্রিং প্রক্রিয়াকরণের জন্য কোড কমাতে সহায়ক।

উপসংহার

C++ তে রেগুলার এক্সপ্রেশন একটি শক্তিশালী টুল যা স্ট্রিং ম্যানিপুলেশনের ক্ষেত্রে অত্যন্ত কার্যকরী। std::regex এর মাধ্যমে আপনি টেক্সটের মধ্যে প্যাটার্ন অনুসন্ধান, প্রতিস্থাপন এবং সেগুলোর উপর অপারেশন সহজভাবে করতে পারেন। এটি প্রোগ্রামিংয়ে টেক্সটের কার্যকরী এবং নমনীয় ম্যানিপুলেশনকে সহজ করে তোলে।

Regular Expressions বা Regex হলো একটি শক্তিশালী টুল, যা একটি নির্দিষ্ট প্যাটার্ন অনুসারে টেক্সট ম্যানিপুলেশন, যেমন খোঁজা, মিলান এবং প্রতিস্থাপন করার কাজ করে। C++ তে regex হেডার ফাইল ব্যবহার করে রেগুলার এক্সপ্রেশন প্রয়োগ করা হয়। রেগুলার এক্সপ্রেশন সাধারণত স্ট্রিং বা টেক্সট ডেটা প্রক্রিয়াকরণে ব্যবহৃত হয় এবং এটি অনেক বেশি কার্যকর যখন টেক্সট থেকে নির্দিষ্ট প্যাটার্ন বের করতে হয়।

Regular Expressions এর মৌলিক ধারণা

রেগুলার এক্সপ্রেশন হলো এমন একটি প্যাটার্ন, যা একটি স্ট্রিং বা টেক্সট থেকে নির্দিষ্ট ফরম্যাট বা প্যাটার্নের টেক্সট খুঁজে বের করতে পারে। এই প্যাটার্নটি বিভিন্ন ধরনের প্রতীক, অক্ষর এবং কন্ট্রোল কাঠামো নিয়ে তৈরি হয়। C++ তে regex হেডারটি std::regex ক্লাস সরবরাহ করে, যা বিভিন্ন ধরণের প্যাটার্নের উপর ভিত্তি করে কাজ করতে পারে।

রেগুলার এক্সপ্রেশন ব্যবহার করার প্রধান কারণসমূহ

• প্যাটার্ন অনুসারে টেক্সট খোঁজা: নির্দিষ্ট প্যাটার্নের টেক্সট খুঁজে বের করার জন্য রেগুলার এক্সপ্রেশন খুবই কার্যকর।
• স্ট্রিং ভ্যালিডেশন: ই-মেইল, ফোন নম্বর, পাসওয়ার্ড ইত্যাদি যাচাই করতে।
• টেক্সট প্রক্রিয়াকরণ: টেক্সট বা ডেটাতে পরিবর্তন করা, প্রতিস্থাপন বা ফরম্যাটিং করতে।
• ডেটা বিশ্লেষণ: বড় টেক্সট বা লগ ফাইল থেকে নির্দিষ্ট তথ্য বের করতে।

C++ এ রেগুলার এক্সপ্রেশন ব্যবহারের উপায়

C++ তে regex হেডারের মাধ্যমে রেগুলার এক্সপ্রেশন প্রয়োগ করা হয়। প্রধান ক্লাস এবং ফাংশনগুলো হলো:

• std::regex: রেগুলার এক্সপ্রেশন তৈরি করার জন্য ব্যবহৃত হয়।
• std::regex_match: পুরো স্ট্রিং প্যাটার্নের সাথে মেলে কিনা তা পরীক্ষা করে।
• std::regex_search: স্ট্রিংয়ের মধ্যে প্যাটার্নের উপস্থিতি খোঁজে।
• std::regex_replace: একটি নির্দিষ্ট প্যাটার্নকে নতুন স্ট্রিং দিয়ে প্রতিস্থাপন করে।

উদাহরণ

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "My email is example@example.com";
    std::regex email_pattern(R"(\w+@\w+\.\w+)");
    
    if (std::regex_search(text, email_pattern)) {
        std::cout << "Valid email found!" << std::endl;
    } else {
        std::cout << "No email found." << std::endl;
    }

    return 0;
}

আউটপুট:

Valid email found!

রেগুলার এক্সপ্রেশন এর কিছু গুরুত্বপূর্ণ প্রতীক

কিছু সাধারণ রেগুলার এক্সপ্রেশন প্যাটার্ন

1. ই-মেইল যাচাইকরণ:

   \w+@\w+\.\w+

   এই প্যাটার্নটি ই-মেইল যাচাই করতে ব্যবহৃত হয়।

2. ফোন নম্বর যাচাইকরণ (১০ ডিজিট):

   \d{10}

3. URL যাচাইকরণ:

   (http|https)://(\w+)(\.\w+)+

4. শুধুমাত্র সংখ্যা:

   ^\d+$

5. শুধুমাত্র অক্ষর:

   ^[a-zA-Z]+$

C++ তে রেগুলার এক্সপ্রেশন এর ব্যবহারিক উদাহরণ

উদাহরণ ১: স্ট্রিং ম্যাচিং

#include <iostream>
#include <regex>

int main() {
    std::string word = "hello";
    std::regex pattern("h.llo");

    if (std::regex_match(word, pattern)) {
        std::cout << "Pattern matched!" << std::endl;
    } else {
        std::cout << "Pattern did not match." << std::endl;
    }

    return 0;
}

উদাহরণ ২: স্ট্রিং প্রতিস্থাপন

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "Hello World!";
    std::regex pattern("World");

    std::string result = std::regex_replace(text, pattern, "Regex");
    std::cout << result << std::endl; // আউটপুট: Hello Regex!

    return 0;
}

উপসংহার

রেগুলার এক্সপ্রেশন C++ এ টেক্সট ম্যানিপুলেশনের জন্য একটি শক্তিশালী টুল। এটি নির্দিষ্ট প্যাটার্নের ভিত্তিতে টেক্সট খুঁজে বের করা, মিলানো এবং প্রতিস্থাপন করার জন্য কার্যকর। C++ এ regex হেডারের মাধ্যমে এটি সহজেই ব্যবহার করা যায়, যা বড় বড় টেক্সট ফাইল বা ডেটা থেকে নির্দিষ্ট তথ্য বিশ্লেষণে সহায়ক।

C++11-এ std::regex লাইব্রেরি অন্তর্ভুক্ত করা হয়েছে, যা রেগুলার এক্সপ্রেশন (Regular Expressions) ব্যবহার করে টেক্সট ম্যানিপুলেশন এবং প্যাটার্ন মেচিংয়ের জন্য ব্যবহৃত হয়। std::regex একটি সিস্টেম্যাটিক এবং কার্যকরী উপায় সরবরাহ করে, যার মাধ্যমে আপনি টেক্সট অনুসন্ধান, প্রতিস্থাপন, ভাগ করা, বা যাচাইকরণের মতো কাজগুলো খুব সহজে করতে পারেন।

std::regex এবং তার সম্পর্কিত ফাংশনগুলির মাধ্যমে আপনি কোনো টেক্সটের মধ্যে একটি নির্দিষ্ট প্যাটার্ন খুঁজে বের করতে পারেন, প্যাটার্নের সাথে মিলে এমন উপাদানগুলি বের করতে পারেন, এবং তাদের উপর বিভিন্ন কাজ (যেমন রিপ্লেসমেন্ট) করতে পারেন।

১. std::regex এর মৌলিক উপাদান

std::regex দুটি প্রধান অংশে বিভক্ত:

1. Regex Object (std::regex): এটি একটি রেগুলার এক্সপ্রেশন স্টোর করে, যা প্যাটার্নকে প্রকাশ করে।
2. Regex Match (std::smatch অথবা std::cmatch): এটি একটি ম্যাচের ফলাফল ধারণ করে, যেখানে আপনি প্যাটার্নের সাথে মিলিত অংশগুলি খুঁজে পাবেন।

২. std::regex এর ফাংশনসমূহ

C++ এর <regex> হেডার ফাইলের অন্তর্গত কিছু গুরুত্বপূর্ণ ফাংশন এবং তাদের ব্যবহার নিচে আলোচনা করা হলো।

১. std::regex_match()

এই ফাংশনটি একটি স্ট্রিংয়ের সাথে সম্পূর্ণ রেগুলার এক্সপ্রেশন মিলিয়ে দেখবে। এটি চেক করে যে স্ট্রিংটি সম্পূর্ণভাবে নির্দিষ্ট প্যাটার্নের সাথে মেলে কিনা।

Syntax:

bool std::regex_match(const std::string& str, const std::regex& rgx);

• str: যে স্ট্রিংটির সাথে প্যাটার্ন মিলাতে হবে।
• rgx: রেগুলার এক্সপ্রেশন।

উদাহরণ:

#include <iostream>
#include <regex>

int main() {
    std::regex pattern("^[a-zA-Z]+$");  // শুধুমাত্র অক্ষর

    std::string text = "HelloWorld";

    if (std::regex_match(text, pattern)) {
        std::cout << "Match found!" << std::endl;
    } else {
        std::cout << "No match found!" << std::endl;
    }

    return 0;
}

আউটপুট:

Match found!

এখানে, std::regex_match() ফাংশনটি পুরো স্ট্রিংটি প্যাটার্নের সাথে মিলিয়ে দেখছে। যদি পুরো স্ট্রিং প্যাটার্নের সাথে মিলে, তবে এটি true রিটার্ন করবে।

২. std::regex_search()

এই ফাংশনটি স্ট্রিংয়ের মধ্যে প্যাটার্ন খুঁজে বের করবে, কিন্তু পুরো স্ট্রিংটি পুরোপুরি মেলানোর প্রয়োজন নেই। এটি প্রথম মিলে যাওয়া প্যাটার্নটি খুঁজে বের করে।

Syntax:

bool std::regex_search(const std::string& str, const std::regex& rgx);

• str: যে স্ট্রিংটি খুঁজতে হবে।
• rgx: রেগুলার এক্সপ্রেশন।

উদাহরণ:

#include <iostream>
#include <regex>

int main() {
    std::regex pattern("World");

    std::string text = "HelloWorld";

    if (std::regex_search(text, pattern)) {
        std::cout << "Match found!" << std::endl;
    } else {
        std::cout << "No match found!" << std::endl;
    }

    return 0;
}

আউটপুট:

Match found!

এখানে, std::regex_search() ফাংশনটি স্ট্রিংয়ের মধ্যে "World" প্যাটার্নটি খুঁজে বের করেছে।

৩. std::regex_replace()

এই ফাংশনটি একটি স্ট্রিংয়ের মধ্যে রেগুলার এক্সপ্রেশন দ্বারা চিহ্নিত অংশগুলিকে নতুন কিছু দ্বারা প্রতিস্থাপন করতে ব্যবহৃত হয়।

Syntax:

std::string std::regex_replace(const std::string& str, const std::regex& rgx, const std::string& fmt);

• str: যে স্ট্রিংটি প্রতিস্থাপন করতে হবে।
• rgx: রেগুলার এক্সপ্রেশন।
• fmt: নতুন টেক্সট যা পুরানো অংশকে প্রতিস্থাপন করবে।

উদাহরণ:

#include <iostream>
#include <regex>

int main() {
    std::regex pattern("world");

    std::string text = "Hello world";

    // "world" কে "C++" দিয়ে প্রতিস্থাপন করা
    std::string newText = std::regex_replace(text, pattern, "C++");

    std::cout << newText << std::endl;  // "Hello C++"

    return 0;
}

আউটপুট:

Hello C++

এখানে, std::regex_replace() "world" কে "C++" দিয়ে প্রতিস্থাপন করেছে।

৪. std::regex_token_iterator

এই ইটরেটরটি রেগুলার এক্সপ্রেশন ব্যবহার করে একটি স্ট্রিংকে ভাঙতে (tokenize) পারে, যেখানে আপনি সেগুলির প্রতিটি অংশ পৃথকভাবে অ্যাক্সেস করতে পারবেন।

Syntax:

std::regex_token_iterator<std::string::iterator> it(begin, end, rgx);

• begin: স্ট্রিংয়ের শুরু।
• end: স্ট্রিংয়ের শেষ।
• rgx: রেগুলার এক্সপ্রেশন।

উদাহরণ:

#include <iostream>
#include <regex>

int main() {
    std::string text = "apple,banana,orange";
    std::regex pattern(",");

    // টোকেনাইজিং করা
    std::sregex_token_iterator it(text.begin(), text.end(), pattern, -1);
    std::sregex_token_iterator end;

    // প্রতিটি টোকেন প্রিন্ট করা
    while (it != end) {
        std::cout << *it << std::endl;
        ++it;
    }

    return 0;
}

আউটপুট:

apple
banana
orange

এখানে, আমরা std::regex_token_iterator ব্যবহার করে কমা (,) দ্বারা পৃথক করা টোকেনগুলিকে আলাদা করেছি এবং প্রিন্ট করেছি।

৫. std::regex_error

এটি একটি এক্সসেপশন ক্লাস যা রেগুলার এক্সপ্রেশন সম্পর্কিত ত্রুটি নির্দেশ করে। এটি সাধারণত তখন ব্যবহৃত হয় যখন একটি অবৈধ রেগুলার এক্সপ্রেশন তৈরি করার চেষ্টা করা হয়।

Syntax:

std::regex_error(std::regex_constants::error_type ec);

• ec: ত্রুটির ধরন (যেমন error_bad_escape, error_bracketing, ইত্যাদি)।

উপসংহার

C++ এর std::regex লাইব্রেরি রেগুলার এক্সপ্রেশন নিয়ে কাজ করার জন্য একটি শক্তিশালী টুল। এর মাধ্যমে আপনি সহজেই টেক্সট অনুসন্ধান, ম্যানিপুলেশন, রিপ্লেসমেন্ট, এবং টোকেনাইজিং করতে পারবেন। এর কিছু গুরুত্বপূর্ণ ফাংশন:

• std::regex_match(): পুরো স্ট্রিংয়ের সাথে প্যাটার্ন মেলানো।
• std::regex_search(): স্ট্রিংয়ের মধ্যে প্যাটার্ন খুঁজে বের করা।
• std::regex_replace(): প্যাটার্নের সাথে মিলিত অংশগুলি প্রতিস্থাপন করা।
• std::regex_token_iterator: স্ট্রিংকে টোকেনাইজ করা।

std::regex লাইব্রেরি ব্যবহার করে আপনি ডেটা যাচাইকরণ, ফরম্যাটিং, অথবা অন্য কোনো টেক্সট ম্যানিপুলেশন কার্য সহজেই সম্পন্ন করতে পারবেন।

স্ট্রিং মেচিং এবং সার্চিং টেকনিক্স হল এমন কৌশল ও অ্যালগরিদম যা একটি স্ট্রিং (বা প্যাটার্ন) খুঁজে বের করতে অন্য স্ট্রিংয়ের মধ্যে অনুসন্ধান করতে ব্যবহৃত হয়। স্ট্রিং মেচিংয়ের প্রয়োজন অনেক ক্ষেত্রেই হয়, যেমন টেক্সট প্রসেসিং, ডেটাবেস অনুসন্ধান, ওয়েব সার্চ ইঞ্জিন, এবং আরও অনেক ক্ষেত্রে।

নিচে কিছু সাধারণ স্ট্রিং মেচিং এবং সার্চিং টেকনিক্সের ব্যাখ্যা এবং উদাহরণ দেয়া হলো:

১. Naive String Matching

এটি একটি সহজতম স্ট্রিং মেচিং অ্যালগরিদম যেখানে প্যাটার্নটি মূল স্ট্রিংয়ের প্রতিটি সম্ভাব্য অবস্থানে পরীক্ষা করা হয়। এটি কেবল একে একে প্রতিটি উপাদান পরীক্ষা করে, ফলে এটি সাধারণত O(n * m) টাইম কমপ্লেক্সিটি সম্পন্ন হয়, যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ:

#include <iostream>
#include <string>

void naiveSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();

    for (int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            std::cout << "Pattern found at index " << i << std::endl;
        }
    }
}

int main() {
    std::string text = "ABABABCABABABAC";
    std::string pattern = "ABAB";
    naiveSearch(text, pattern);
    return 0;
}

আউটপুট:

Pattern found at index 0
Pattern found at index 7
Pattern found at index 12

২. Knuth-Morris-Pratt (KMP) Algorithm

KMP অ্যালগরিদম স্ট্রিং মেচিংয়ের জন্য একটি কার্যকরী কৌশল যা preprocessing পদ্ধতি ব্যবহার করে। এটি প্যাটার্নের মধ্যে লজিক্যাল স্নেহমূলক সম্পর্কগুলো অনুসন্ধান করে, যাতে পুনরাবৃত্তি হীনভাবে স্ট্রিংয়ের মধ্যে প্যাটার্নটি খুঁজে পাওয়া যায়। এর টাইম কমপ্লেক্সিটি হল O(n + m), যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ:

#include <iostream>
#include <vector>
#include <string>

std::vector<int> computeLPSArray(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int len = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            ++len;
            lps[i] = len;
            ++i;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                ++i;
            }
        }
    }
    return lps;
}

void KMPSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    std::vector<int> lps = computeLPSArray(pattern);

    int i = 0;
    int j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            ++i;
            ++j;
        }

        if (j == m) {
            std::cout << "Pattern found at index " << i - j << std::endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                ++i;
            }
        }
    }
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}

আউটপুট:

Pattern found at index 10

৩. Boyer-Moore Algorithm

Boyer-Moore অ্যালগরিদম হল একটি খুব কার্যকরী স্ট্রিং মেচিং অ্যালগরিদম, যা প্যাটার্নের অনুসন্ধানে two heuristics ব্যবহার করে:

• Bad Character Heuristic: যখন কোনো অক্ষর মেলে না, তখন প্যাটার্নটি কতটা এগিয়ে যেতে পারে তা নির্ধারণ করে।
• Good Suffix Heuristic: যদি কোনো অংশ মেলে না, তবে পূর্ববর্তী মেলানো অংশের সাহায্যে প্যাটার্নটি কোথায় যাবে তা নির্ধারণ করে।

এটি O(n/m) গড় সময়ে কাজ করে, যেখানে n হল মূল স্ট্রিংয়ের দৈর্ঘ্য এবং m হল প্যাটার্নের দৈর্ঘ্য। তবে, এর পারফরম্যান্স অনেক ক্ষেত্রে বেশি ভালো হয়।

উদাহরণ:

#include <iostream>
#include <string>
#include <vector>

void badCharacterHeuristic(const std::string& pattern, std::vector<int>& badChar) {
    int m = pattern.length();
    for (int i = 0; i < m; ++i) {
        badChar[pattern[i]] = i;
    }
}

void BMSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    std::vector<int> badChar(256, -1); // ASCII size

    badCharacterHeuristic(pattern, badChar);

    int s = 0; // Shift
    while (s <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[s + j]) {
            --j;
        }

        if (j < 0) {
            std::cout << "Pattern found at index " << s << std::endl;
            s += (s + m < n) ? m - badChar[text[s + m]] : 1;
        } else {
            s += std::max(1, j - badChar[text[s + j]]);
        }
    }
}

int main() {
    std::string text = "ABAAABCDABCABC";
    std::string pattern = "ABC";
    BMSearch(text, pattern);
    return 0;
}

আউটপুট:

Pattern found at index 7
Pattern found at index 12

৪. Rabin-Karp Algorithm

Rabin-Karp অ্যালগরিদম একটি স্ট্রিং মেচিং অ্যালগরিদম যা হ্যাশিং ব্যবহার করে প্যাটার্ন এবং সাবস্ট্রিংগুলির হ্যাশ মান তুলনা করে। এটি সাধারণত O(n + m) গড় সময়ে কাজ করে, তবে খারাপ কেসে O(n * m) সময়ে চলে।

উদাহরণ:

#include <iostream>
#include <string>
#include <cmath>

const int d = 256;  // Character set size
const int q = 101;  // A prime number for modulo

void rabinKarpSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    int i, j;
    int p = 0;  // hash value for pattern
    int t = 0;  // hash value for text
    int h = 1;

    // Calculate h = pow(d, m-1) % q
    for (i = 0; i < m - 1; i++) {
        h = (h * d) % q;
    }

    // Calculate the hash value of pattern and text
    for (i = 0; i < m; i++) {
        p = (d * p + pattern[i]) % q;
        t = (d * t + text[i]) % q;
    }

    // Slide the pattern over text
    for (i = 0; i <= n - m; i++) {
        if (p == t) {
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == m) {
                std::cout << "Pattern found at index " << i << std::endl;
            }
        }

        // Calculate hash value for next window of text
        if (i < n - m) {
            t = (d * (t - text[i] * h) + text[i + m]) % q;
            if (t < 0) {
                t = t + q;
            }
        }
    }
}

int main() {
    std::string text = "ABC ABCDAB ABCDABCDABDE";
    std::string pattern = "

ABCDABD";
    rabinKarpSearch(text, pattern);
    return 0;
}

আউটপুট:

Pattern found at index 15

উপসংহার

• Naive String Matching: সহজ এবং সরল পদ্ধতি, তবে বড় ডেটাসেটে কার্যকর নয়।
• KMP Algorithm: একটি প্রগতিশীল পদ্ধতি যা আগে থেকে প্যাটার্নের প্রক্রিয়া করে, দ্রুত কাজ করে।
• Boyer-Moore Algorithm: অত্যন্ত কার্যকরী এবং খারাপ কেসে অপটিমাইজ করা, দ্রুত কাজ করে।
• Rabin-Karp Algorithm: হ্যাশিং ব্যবহার করে, যা দ্রুত গড় পারফর্মেন্স দেয়, তবে খারাপ কেসে ধীর হতে পারে।

এই অ্যালগরিদমগুলি ব্যবহার করে আপনি স্ট্রিং মেচিংয়ের কার্যকারিতা এবং দক্ষতা বৃদ্ধি করতে পারেন।

সি++ এ Substitution এবং Complex Pattern Matching (জটিল প্যাটার্ন ম্যাচিং) করার জন্য std::regex লাইব্রেরি ব্যবহার করা হয়, যা C++11 এ প্রবর্তিত হয়েছে। এটি একটি শক্তিশালী টুল যা বিভিন্ন রেগুলার এক্সপ্রেশন প্যাটার্ন তৈরি, পরীক্ষা, এবং পরিচালনা করতে ব্যবহার করা যায়। এই লাইব্রেরি ব্যবহার করে পাঠ্য ডেটাতে জটিল নিয়মের ভিত্তিতে খোঁজা, প্রতিস্থাপন, বা টেক্সট ম্যানিপুলেশন সহজে করা যায়।

Substitution

Substitution হলো এমন একটি প্রক্রিয়া যেখানে একটি নির্দিষ্ট প্যাটার্ন মিলে গেলে সেটি নতুন কোনো টেক্সট দ্বারা প্রতিস্থাপিত হয়। C++ এ std::regex_replace ফাংশনটি এটি সম্পন্ন করতে ব্যবহার করা হয়।

উদাহরণ: সরল প্রতিস্থাপন

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "The quick brown fox jumps over the lazy dog.";
    std::regex pattern("fox");
    
    // 'fox' শব্দটি 'cat' শব্দে প্রতিস্থাপন করা
    std::string result = std::regex_replace(text, pattern, "cat");
    
    std::cout << result << std::endl; // আউটপুট: The quick brown cat jumps over the lazy dog.

    return 0;
}

এখানে regex_replace ফাংশন pattern ("fox") কে খুঁজে এবং "cat" দ্বারা প্রতিস্থাপন করে। এর ফলে আউটপুটে "fox" এর পরিবর্তে "cat" দেখা যায়।

উদাহরণ: গ্রুপিং এবং প্লেসহোল্ডার ব্যবহার করে প্রতিস্থাপন

std::regex_replace গ্রুপিং এবং প্লেসহোল্ডার ব্যবহার করে আরও জটিল প্রতিস্থাপন করতে পারে। উদাহরণস্বরূপ, প্রতিস্থাপনের সময় নির্দিষ্ট গ্রুপগুলো ব্যবহার করা যেতে পারে।

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "My email is example@test.com";
    std::regex pattern(R"((\w+)(@)(\w+\.\w+))");
    
    // ইমেইল ঠিকানার অংশ গুলো আংশিক প্রতিস্থাপন
    std::string result = std::regex_replace(text, pattern, "$1[at]$3");

    std::cout << result << std::endl; // আউটপুট: My email is example[at]test.com

    return 0;
}

এখানে, (\w+) এবং (\w+\.\w+) দিয়ে ইমেইলের অংশগুলো ক্যাপচার করা হয়েছে, এবং $1 এবং $3 ব্যবহার করে আউটপুটে আংশিকভাবে প্রতিস্থাপন করা হয়েছে।

Complex Pattern Matching

Complex Pattern Matching করার জন্য std::regex_search এবং std::regex_match ব্যবহার করা হয়। এটি টেক্সট থেকে নির্দিষ্ট নিয়ম অনুযায়ী প্যাটার্ন খুঁজতে সাহায্য করে। regex_match পুরো স্ট্রিং মিললে সত্য রিটার্ন করে, আর regex_search স্ট্রিংয়ের ভেতরে প্যাটার্ন মিল খুঁজে পেলে সত্য রিটার্ন করে।

উদাহরণ: সরল প্যাটার্ন ম্যাচিং

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "My phone number is 123-456-7890";
    std::regex pattern(R"(\d{3}-\d{3}-\d{4})");

    if (std::regex_search(text, pattern)) {
        std::cout << "Phone number found!" << std::endl;
    } else {
        std::cout << "Phone number not found." << std::endl;
    }

    return 0;
}

উপরের উদাহরণে, \d{3}-\d{3}-\d{4} প্যাটার্নটি একটি ফোন নম্বর মেলে (যেমন "123-456-7890") এবং regex_search ফাংশন এই প্যাটার্নের উপর ভিত্তি করে ম্যাচ খুঁজে পায়।

উদাহরণ: Complex Pattern Matching with Groups

গ্রুপিং এবং অগ্রগতি শর্ত ব্যবহার করে আরও জটিল প্যাটার্ন তৈরি করা যায়।

#include <iostream>
#include <regex>
#include <string>

int main() {
    std::string text = "Product code: ABC-1234";
    std::regex pattern(R"((\w+)-(\d+))");

    std::smatch match;
    if (std::regex_search(text, match, pattern)) {
        std::cout << "Full match: " << match.str(0) << std::endl;
        std::cout << "Part 1: " << match.str(1) << std::endl; // ABC
        std::cout << "Part 2: " << match.str(2) << std::endl; // 1234
    }

    return 0;
}

এখানে (\w+)-(\d+) প্যাটার্নটি "ABC-1234" এর মতো প্রোডাক্ট কোড মেলে, এবং smatch অবজেক্টের মাধ্যমে আলাদা করে গ্রুপগুলোর মান বের করা হয়েছে।

সংক্ষেপে

• Substitution (প্রতিস্থাপন): std::regex_replace ব্যবহার করে নির্দিষ্ট প্যাটার্ন খুঁজে নতুন মান দিয়ে প্রতিস্থাপন করা যায়। গ্রুপিং এবং প্লেসহোল্ডার ব্যবহার করে আরও জটিল সাবস্টিটিউশন করা সম্ভব।
• Complex Pattern Matching (জটিল প্যাটার্ন ম্যাচিং): std::regex_search এবং std::regex_match ব্যবহার করে টেক্সটে জটিল নিয়ম অনুযায়ী প্যাটার্ন খুঁজে বের করা যায়। গ্রুপিং ব্যবহার করে নির্দিষ্ট অংশগুলো আলাদা করে পাওয়া যায়।

সি++ এ std::regex লাইব্রেরি ব্যবহার করে সহজে ও কার্যকরভাবে জটিল প্যাটার্ন ম্যাচিং এবং সাবস্টিটিউশন করা যায়, যা ডেটা প্রসেসিং ও টেক্সট ম্যানিপুলেশনের জন্য অত্যন্ত উপযোগী।