ある文字列を別の文字列と等しくするために削除する必要がある最長の部分文字列の長さ

この記事では、ある文字列を別の文字列と等しくするために削除する必要がある最長の部分文字列の長さを見つける問題について説明します。まず問題の内容を理解してから、問題を解決するためのシンプルで効率的な方法と、それぞれのアルゴリズムと時間の複雑さを検討します。最後に、C でソリューションを実装します。

＃＃＃問題文＃＃＃

2 つの文字列 A と B が与えられた場合、文字列 B と等しくなるように文字列 A から削除する必要がある最長の部分文字列の長さを決定します。

単純な方法

最も簡単な方法は、文字列 A の可能なすべての部分文字列を生成し、それらを 1 つずつ削除し、結果の文字列が文字列 B と等しいかどうかを確認することです。そうであれば、削除された部分文字列の長さを保存します。最後に、削除されたすべての部分文字列の最大長を返します。

アルゴリズム (単純)

maxLength を 0 に初期化します。
文字列 A

• の考えられるすべての部分文字列を生成します

各部分文字列について、文字列 A からそれを削除し、結果の文字列が文字列 B と等しいかどうかを確認します。
「はい」の場合、maxLength を maxLength と削除された部分文字列の長さの間の最大値に更新します。
最大長を返します。
C コード (プレーン)

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 (単純)

- O(n^3)、n は文字列 A の長さです。

効率的な方法

この問題を解決する効果的な方法は、2 つの文字列の最長共通部分列 (LCS) を見つけることです。文字列 B と等しくなるように文字列 A 内で削除する必要がある最長の部分文字列の長さは、文字列 A の長さと LCS の長さの差です。 アルゴリズム (効率的)

文字列 A と文字列 B の最長共通部分列 (LCS) を見つけます。
文字列 A の長さと LCS の長さの差を返します。
C コード (効率的)
• リーリー ＃＃＃出力＃＃＃ リーリー
  時間計算量 (効率的)
- O(m * n)。ここで、m は文字列 A の長さ、n は文字列 B の長さです。

＃＃＃結論は＃＃＃

この記事では、ある文字列を別の文字列と等しくするために削除する必要がある最長の部分文字列の長さを見つける問題を検討します。この問題を解決するためのシンプルかつ効率的な方法と、そのアルゴリズムと時間の複雑さについて説明します。効率的な方法は最長共通部分列の概念を活用し、単純な方法と比較して時間計算量の大幅な改善を達成します。

以上がある文字列を別の文字列と等しくするために削除する必要がある最長の部分文字列の長さの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。