C++ প্রোগ্রাম: ভেক্টর ব্যবহার করে স্ট্রিং ম্যাচিং

এটি স্ট্রিং ম্যাচিংয়ের আরেকটি পদ্ধতি। এই অ্যাপ্রোচে, আমরা ভেক্টর ব্যবহার করে একটি সাবস্ট্রিং সার্চ করব।

C++-এ স্ট্যান্ডার্ড লাইব্রেরি ব্যবহার করে সহজেই ভেক্টর তৈরি করা যায়। আমরা মেইন স্ট্রিং এবং সার্চ করার স্ট্রিংকে ভেক্টর হিসেবে নেব, তারপর সেটা মেইন স্ট্রিং-এ সার্চ করব। একবার ম্যাচ পাওয়া গেলে ফাংশন অ্যাড্রেস রিটার্ন করে, এবং মেইন স্ট্রিং থেকে সেটা রিমুভ করে দেয়। তাই পরবর্তী ইটারেশনে এটি লোকেশন ০ থেকে আবার সার্চ শুরু করে।

একাধিক অকরেন্সের জন্য লুপ ব্যবহার করে বারবার ম্যাচ সার্চ করা হয় এবং পজিশন রিটার্ন করা হয়।

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC"
Output: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

অ্যালগরিদম

vector_pattern_search(main, substr)

ইনপুট − মেইন টেক্সট এবং সাবস্ট্রিং।

আউটপুট − যেখানে প্যাটার্ন পাওয়া গেল সেসব লোকেশন।

Begin
    p := মেইন স্ট্রিংয়ের শুরুর পয়েন্ট
    while r substr-এর শেষে নয় এবং p main-এর শেষে নয়
        r := substr-এর শুরু
        while p-এ থাকা আইটেম এবং r-এ থাকা আইটেম এক নয়, এবং p main-এ আছে
            p := p + 1
            i := i + 1
        done
        q := p
        while p-এ থাকা আইটেম এবং r-এ থাকা আইটেম এক হয়, এবং r substr-এ এবং p main-এ আছে
            p := p + 1
            i := i + 1
            r := r + 1
        done
        if r substr-এর শেষে পৌঁছায়
            main-এ서 substr-এর প্রথম অকরেন্স ডিলিট করুন
            যেখানে substr পাওয়া গেল সেটা রিটার্ন করুন
        if p main স্ট্রিংয়ের শেষে পৌঁছায়
            return 0
        q := q + 1
        p := q
    done
End

উদাহরণ কোড

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void take_string(vector<char> &string) { /* ... */ }
void display(vector<char> string) { /* ... */ }

int match_string(vector<char>& main, vector<char> substr) {
    vector<char>::iterator p, q, r;
    int i = 0;
    p = main.begin();
    while (r <= substr.end() && p <= main.end()) {
        r = substr.begin();
        while (*p != *r && p < main.end()) { p++; i++; }
        q = p;
        while (*p == *r && r <= substr.end() && p <= main.end()) { p++; i++; r++; }
        if (r >= substr.end()) {
            main.erase(main.begin(), q + 1);
            return (i - substr.size() + 1);
        }
        if (p >= main.end()) return 0;
        p = ++q;
    }
}

আউটপুট

Enter main String: C++ is programming language. It is object oriented language
Enter substring to find: language
Match found at Position = 20
Match found at Position = 52