C++で文字列が他の文字列の部分列（サブシーケンス）かどうかを判定するプログラム

問題概要

2つの文字列 S と T が与えられ、「S は T の部分列（サブシーケンス）であるか」を判定する問題です。部分列とは、元の文字列からいくつかの文字を削除して得られる文字列で、残った文字の並び順は元のまま保たれているものを指します。

例えば、S = "abc"、T = "adbrcyxd" の場合、'a'、'b'、'c' がそれぞれ T の中に順番どおり現れるため、出力は True になります。

解き方（アルゴリズム）

この問題は、2つのポインタを使った貪欲法（グリーディ法）で効率よく解くことができます。手順は以下の通りです。

• s と t が完全に一致する場合は、true を返します。

• n := s のサイズ、m := t のサイズ とし、ポインタ j := 0 で初期化します。

• i := 0 から始めて i < n の間、i を1ずつ増やしながら以下を繰り返します。

  • t[j] が s[i] と一致したら、j を1増やします。

  • j が t のサイズに達したら、必要な文字をすべて順番に見つけたことになるため、true を返します。

• ループが終了しても true にならない場合は、部分列ではないため false を返します。

C++での実装例

それでは、理解を深めるために以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(string t, string s) {
        if(s == t)
        return true;
        int n = s.size();
        int m = t.size();
        int j = 0;
        for(int i = 0; i < n; i++){
            if(t[j] == s[i])
            j++;
            if(j == t.size())
            return true;
        }
        return false;
    }
};
main(){
    Solution ob;
    string S = "abc", T = "adbrcyxd";
    cout << ob.solve(S, T);
}

入力

"abc", "adbrcyxd"

出力

1

計算量の目安

この手法では文字列 s を一度だけ走査するため、時間計算量は O(n)（n は s の長さ）、追加のメモリ使用量は O(1) で済みます。部分列判定において非常に効率的なアプローチといえます。