สมมติว่าเรามีอาร์เรย์ขนาด 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
