ধরুন আমাদের m এবং n আকারের দুটি অ্যারে আছে, কাজটি হল প্রথম অ্যারেতে ন্যূনতম দৈর্ঘ্যের সাব্যারে খুঁজে বের করা, যেটিতে দ্বিতীয় অ্যারে থাকলে সমস্ত উপাদান রয়েছে। দ্বিতীয় অ্যারের উপাদানটি বড় অ্যারেতে অ-সংলগ্ন অবস্থায় থাকতে পারে তবে ক্রম একই হতে হবে। সুতরাং যদি দুটি অ্যারে হয় A =[2, 2, 4, 5, 8, 9], এবং B =[2, 5, 9], তাহলে আউটপুট হবে 5। A-এর ক্ষুদ্রতম সাববারে হিসাবে, হবে [ 2, 4, 5, 8, 9]। এখানে সমস্ত উপাদান যেমন [2, 5, 9] একই ক্রমে রয়েছে। তাই আকার 5.
আমরা দ্বিতীয় অ্যারের প্রথম এলিমেন্টের সাথে প্রথম এলিমেন্টের মিল যাচাই করে এটি সমাধান করতে পারি। যখন প্রথম এলিমেন্ট মিলে যায়, তখন আমরা মেইন অ্যারের দ্বিতীয় অ্যারের বাকি উপাদানগুলোর সাথে ম্যাচ করি, যখন সব উপাদান মিলে যায়, প্রয়োজনে দৈর্ঘ্য আপডেট করি। এটি করার পরে সাবয়ারের ন্যূনতম দৈর্ঘ্য ফেরত দিন।
উদাহরণ
#include<iostream>
using namespace std;
int lengthMinSubarray(int A[], int n, int B[], int m) {
int res = INT_MAX;
for (int i = 0; i < n - m + 1; i++) {
if (A[i] == B[0]) {
int j = 0, idx = i;
for (; idx < n; idx++) {
if (A[idx] == B[j])
j++;
if (j == m)
break;
}
if (j == m && res > idx - i + 1)
res = (idx == n) ? idx - i : idx - i + 1;
}
}
return res;
}
int main() {
int A[] = { 5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7 };
int B[] = { 5, 5, 7 };
int n = sizeof(A)/sizeof(A[0]);
int m = sizeof(B)/sizeof(B[0]);
cout << "Minimum length of subarray: " << lengthMinSubarray(A, n, B, m);
} আউটপুট
Minimum length of subarray: 3
