C++で同じ順序ですべての要素を含む最小の部分配列を見つける方法

サイズ m と n の2つの配列があるとします。このとき、1つ目の配列の中から、2つ目の配列のすべての要素を含む最小長の部分配列（サブ配列）を見つけるのが課題です。

重要なポイントとして、2つ目の配列の要素は1つ目の配列内で連続していなくても構いませんが、出現する順序は同じでなければなりません。

具体例

例えば、次のような2つの配列を考えてみましょう。

• A = [2, 2, 4, 5, 8, 9]
• B = [2, 5, 9]

この場合、出力は 5 になります。なぜなら、A の中で条件を満たす最小の部分配列は [2, 4, 5, 8, 9] であり、B の要素 [2, 5, 9] がすべて同じ順序で含まれているからです。したがって、そのサイズは 5 となります。

解法のアプローチ

この問題は、以下の手順で解決できます。

1. 1つ目の配列を走査し、2つ目の配列の先頭要素と一致する位置を探します。
2. 先頭要素が一致したら、その位置以降で2つ目の配列の残りの要素を順番に照合します。
3. すべての要素が一致した時点で、その部分配列の長さを計算し、これまでの最小値より短ければ更新します。
4. すべての候補について処理を終えた後、部分配列の最小長を返します。

C++による実装例

#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

この例では、配列 A = [5, 6, 5, 2, 7, 5, 6, 7, 5, 5, 7] の中から、B = [5, 5, 7] のすべての要素を同じ順序で含む最小の部分配列が見つかり、その長さ 3 が出力されます。

まとめ

このアルゴリズムは、先頭要素の一致を起点として貪欲に照合を進めるシンプルな手法です。計算量は O(n × m) 程度となり、配列のサイズがそれほど大きくない場合には十分に実用的です。要素の順序を保ちながら部分配列を探索する際の基本的な考え方として、ぜひ参考にしてください。