मान लीजिए कि हमारे पास 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