1. 概要

このチュートリアルでは、文字列内のサブシーケンスの出現回数を見つける問題について説明します。 まず、問題を定義します。 次に、それを説明するための例を示します。 最後に、この問題を解決するための3つの異なるアプローチを紹介します。

2. 問題の定義

文字列と文字列があります。 文字列が文字列内に出現する回数をサブシーケンスとしてカウントしたいと思います。

文字列のサブシーケンスは、残りの要素の順序を変更せずに0個以上の要素を削除することにより、指定された文字列から派生できるシーケンスです。

理解を深めるために、次の例を見てみましょう。

与えられた文字列と文字列：

文字列内の文字列の出現回数をサブシーケンスとして数えましょう。

ご覧のとおり、stringと等しいstringのサブシーケンスが3つあります。 したがって、与えられた例に対する答えはです。

3. 再帰的アプローチ

このアプローチの主なアイデアは、文字列のすべての可能なサブシーケンスを試し、それが文字列と一致するかどうかを確認することです。

文字列の文字ごとに、2つのオプションがあります。 現在のサブシーケンスで考慮されないようにそのままにして、次の文字に移動します。 それ以外の場合は、文字列の現在の文字と等しい場合は、サブシーケンスの文字と見なすことができます。

文字列の最後に到達すると、文字列と等しい文字列のサブシーケンスを取得します。 その結果、サブシーケンスの数が1つ増えます。 それ以外の場合は、現在のサブシーケンスを無視します。

3.1. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、文字列に一致する文字列のサブシーケンスの数を返す関数を宣言します。 関数には2つのパラメーターとがあり、それぞれ文字列との現在の位置を表します。

まず、再帰関数を扱っているので、答えの検索を停止するための基本条件を設定します。 処理しなければならない状況は2つあります。

  1. との終わりに到達すると、文字列に一致するのサブシーケンスを取得したことを意味するため、サブシーケンスの数を増やすために戻ります。
  2. 文字列の終わりに到達した場合、それは。の終わりに到達しなかったことを意味します。 したがって、に一致するサブシーケンスが見つからなかったため、を返します。

次に、再帰呼び出しを設定する必要があります。 の文字ごとに、2つのオプションがあります。 現在の文字を選択するか、そのままにしておくことができます：

  1. 選択：の現在の文字がの現在の文字と一致する場合、それを取得して両方のポインターを前方に移動しようとします。
  2. 残す：の各文字について、サブシーケンスからも考慮する必要があります。 したがって、それを残して、前方のポインタのみを移動しようとします。

これらの2つの再帰呼び出しの合計は、最終的には現在の状態に対する答えになります。

最後に、は文字列に一致する文字列のサブシーケンスの数を返します。

3.2. 複雑さ

このアルゴリズムの時間計算量はです。ここで、は文字列の長さ、は文字列の長さです。 この複雑さの理由は、文字列の各文字について、それを取るか残すかという2つの選択肢があるためです。 ただし、ピッキング手順は、内の文字数に制限されています。 だから、それは私たちにの全体的な複雑さを与えます。

このアルゴリズムのスペースの複雑さは、です。これは、文字列内の次の文字に移動するたびに、再帰ツリーの深さが最大であるためです。

4. 動的計画法アプローチ

以前のアプローチの非常に複雑な点は、各状態を複数回計算することです。 このアプローチでは、各状態の答えを記憶して、その状態を再度計算せずに将来使用できるようにします。

前のアプローチで見たように、状態の答えは状態の答えと状態に依存します。 したがって、状態を計算する前に、を計算します。 次に、前の回答に基づいて状態の回答を計算します。

最後に、私たちの問題に対する答えは、状態の答えに保存されます。

4.1. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、各状態の回答を格納する配列を宣言します。 これは前のアプローチの基本ケースであったため、状態の初期値はに等しくなります。

次に、文字列の最後から最初まで繰り返します。 文字列の位置ごとに、文字列の最後から最初まで繰り返します。これは、すべての状態がその後の状態に依存しているためです。

状態ごとに、両方の文字列の現在の文字が一致するかどうかを確認します。 その場合、現在の状態の回答に状態の回答を追加します。これは、文字列の現在の文字を選択したことを意味します。 さらに、状態の答えを追加します。これは、文字列の現在の文字を残すことを意味します。

最後に、の値は、両方の文字列の先頭から開始した場合に、文字列に一致する文字列のサブシーケンスの数に等しくなります。

4.2. 複雑さ

このアルゴリズムの複雑さはです。ここで、は文字列の長さ、は文字列の長さです。 この複雑さの理由は、文字列の各文字について、文字列のすべての文字を反復処理し、前に計算した状態に応じて各状態を個別に解決しようとするためです。

このアルゴリズムのスペースの複雑さは、です。これは、各状態の回答を格納するために使用するメモ化配列のサイズです。

5. 動的計画法の最適化

このアプローチでは、前のアプローチのスペースの複雑さを最適化します。 ここでの主な考え方は、前のアプローチと同じです。 唯一の違いは、各状態が次の状態にのみ依存することです。ここで、は文字列の任意の位置を表します。メモ化配列の最初の次元を（文字列の長さ）の代わりに減らすことができます。

状態ごとに、次の状態の交互の位置に保存しようとします。 そのために、mod演算子を利用します。 つまり、現在の状態、または次の状態になります。

結局、私たちの問題に対する答えは、状態の答えにも保存されます。

5.1. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、各状態の回答を格納する配列を宣言します。 ここでは基本ケースであるため、状態の初期値はに等しくなります。

次に、前のアプローチと同じことを行いますが、元のインデックスを最初の次元に配置する代わりに、そのモジュールを。で配置します。

最後に、の値は、両方の文字列の先頭から開始した場合に、文字列に一致する文字列のサブシーケンスの数に等しくなります。

5.2. 複雑さ

このアルゴリズムの複雑さはです。ここで、は文字列の長さ、は文字列の長さです。 この複雑さの理由は、前のアプローチと同じです。

このアルゴリズムのスペースの複雑さは、です。これは、各状態の回答を格納するために使用するメモ化配列のサイズです。 文字列内の各位置の答えは次の位置の答えにのみ依存するため、最初の次元はに等しくなります。

6. 結論

この記事では、文字列内のサブシーケンスの出現回数を見つける問題を紹介しました。

まず、問題を説明する例を示しました。 次に、それを解決するための3つの異なるアプローチを検討しました。

最後に、それらの実装について説明しました。各アプローチのスペースまたは時間の複雑さは、前のアプローチよりも優れています。