C++で同じ順序ですべての要素を含む最小のサブ配列を検索します

サイズmとnの2つの配列があるとします。タスクは、最初の配列で最小長のサブ配列を見つけることです。これには、2番目の配列の場合はすべての要素が含まれます。 2番目の配列の要素は、大きな配列に連続していない場合がありますが、順序は同じである必要があります。したがって、2つの配列がA =[2、2、4、5、8、9]、B =[2、5、9]の場合、出力は5になります。Aの最小のサブ配列として、は[ 2、4、5、8、9]。ここでは、[2、5、9]のようなすべての要素が同じ順序になっています。したがって、サイズは5です。

これは、最初の要素が2番目の配列の最初の要素と一致することを確認することで解決できます。最初の要素が一致したら、メイン配列の2番目の配列の残りの要素と一致し、すべての要素が一致したら、必要に応じて長さを更新します。これを行った後、サブアレイの最小長を返します。

例

#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