C++에서 모든 요소를 ​​같은 순서로 포함하는 가장 작은 부분배열 찾기

크기가 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