C++-এ সাবস্ট্রিং যাতে সব শব্দের সংযোগ থাকে (Substring with Concatenation of All Words)

ধরি আমাদের একটি স্ট্রিং s এবং একটি শব্দের তালিকা words আছে, যেখানে সব শব্দের দৈর্ঘ্য একই। আমাদের s-এ সেই সাবস্ট্রিংগুলোর শুরুতে ইনডেক্স বের করতে হবে যেগুলো words-এ থাকা প্রতিটি শব্দকে ঠিক একবার করে এবং কোনো অতিরিক্ত ক্যারেক্টার ছাড়া সংযুক্ত (concatenation) করে তৈরি।

উদাহরণস্বরূপ, যদি ইনপুট হয় "barfoothefoobarman" এবং words = ["foo", "bar"], তবে আউটপুট হবে [0, 9]। কারণ ইনডেক্স 0 এবং 9-এ শুরু হওয়া সাবস্ট্রিংগুলো যথাক্রমে "barfoo" এবং "foobar"।

সমাধানের ধাপসমূহ

• ok() মেথড সংজ্ঞায়িত করা: এটি স্ট্রিং s, ম্যাপ wordCnt এবং n নিবে।
  • s-কে temp-এ কপি করা।
  • i = n থেকে s.size()-1 পর্যন্ত লুপ:
    • যদি temp.size() n-র গুণিতক হয়:
      • যদি temp wordCnt-এ না থাকে, তবে false ফেরত।
      • অন্যথায় যদি wordCnt[temp] == 1 হয়, তবে wordCnt থেকে temp ডিলিট করে temp খালি করা।
      • অন্যথায় wordCnt[temp] এক কমিয়ে temp খালি করা।
    • temp += s[i]
  • শেষে temp wordCnt-এ আছে কিনা চেক করা এবং উপরের মতো প্রসেস করা।
  • wordCnt.size() == 0 হলে true ফেরত।
• মেইন মেথড থেকে:
  • যদি a বা b খালি হয়, তবে খালি অ্যারে ফেরত।
  • wordCnt ম্যাপে b-র শব্দগুলোয় ফ্রিকোয়েন্সি স্টোর করা।
  • ans অ্যারে তৈরি।
  • window := words.size() * words[0].size()
  • a-কে temp-এ কপি করা।
  • i = window থেকে a.size()-1 পর্যন্ত লুপ:
    • যদি temp.size() window-র গুণিতক হয় এবং ok(temp, wordCnt, words[0].size()) true হয়, তবে i - window ans-এ পুশ করা।
    • temp += a[i]
    • যদি temp.size() > window হয়, তবে temp.erase(0, 1)
  • শেষে একবার আর চেক করে ans-এ পুশ করা।
  • ans ফেরত।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    bool ok(string s, unordered_map wordCnt, int n) {
        string temp = "";
        for (int i = 0; i < n; i++) {
            temp += s[i];
        }
        for (int i = n; i < s.size(); i++) {
            if (temp.size() % n == 0) {
                if (wordCnt.find(temp) == wordCnt.end()) return false;
                else {
                    if (wordCnt[temp] == 1) {
                        wordCnt.erase(temp);
                        temp = "";
                    } else {
                        wordCnt[temp]--;
                        temp = "";
                    }
                }
            }
            temp += s[i];
        }
        if (wordCnt.find(temp) == wordCnt.end()) return false;
        else {
            if (wordCnt[temp] == 1) {
                wordCnt.erase(temp);
                temp = "";
            } else {
                wordCnt[temp]--;
                temp = "";
            }
        }
        return wordCnt.size() == 0;
    }
    vector findSubstring(string a, vector& b) {
        if (a.size() == 0 || b.size() == 0) return {};
        unordered_map wordCnt;
        for (int i = 0; i < b.size(); i++) wordCnt[b[i]]++;
        vector ans;
        int window = b.size() * b[0].size();
        string temp = "";
        for (int i = 0; i < window; i++) temp += a[i];
        for (int i = window; i < a.size(); i++) {
            if (temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())) {
                ans.push_back(i - window);
            }
            temp += a[i];
            if (temp.size() > window) temp.erase(0, 1);
        }
        if (temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
            ans.push_back(a.size() - window);
        return ans;
    }
};

int main() {
    vector v = {"foo", "bar"};
    Solution ob;
    print_vector(ob.findSubstring("barfoothefoobarman", v));
}

ইনপুট

"barfoothefoobarman", ["foo", "bar"]

আউটপুট

[0, 9]