Giả sử có hai mảng kích thước m và n. Nhiệm vụ tìm mảng con độ dài nhỏ nhất trong mảng đầu tiên chứa tất cả phần tử của mảng thứ hai. Phần tử mảng thứ hai có thể xuất hiện không liên tục trong mảng lớn nhưng thứ tự phải giống nhau. Nếu A = [2, 2, 4, 5, 8, 9], B = [2, 5, 9], kết quả 5. Mảng con nhỏ nhất của A là [2, 4, 5, 8, 9]. Tất cả [2, 5, 9] cùng thứ tự. Kích thước 5.
Giải quyết bằng cách kiểm tra phần tử đầu khớp với phần tử đầu mảng thứ hai. Khi khớp, khớp tiếp các phần tử còn lại của mảng thứ hai trong mảng chính, khi khớp hết cập nhật độ dài nếu cần. Sau đó trả về độ dài nhỏ nhất.
Ví dụ mã nguồn
#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); } Kết quả
Minimum length of subarray: 3