1

2 つの文字列があるとします。

"hello"
"love"

文字列の最大部分配列のサイズは 2: "lo" です。

別の例を次に示します。

"ABBABBA"
"BBABCBA"
Maximum subarray: "BBAB"
Size: 4

基本的に、この問題を最も効率的な方法で解決するにはどうすればよいですか?

私の考えは次のとおりです。

  • 1 つの文字列のすべての部分配列を生成する
  • 他の文字列のすべての部分配列を生成します。
  • すべての部分配列を比較する
  • 結果は、一致する最大のサブ配列のサイズです

しかし、これは見栄えの悪いブルートフォースだと思います。どうすればこれを改善できるか考えていますか?

ありがとうございました！

EDIT 文字列も必要です。

4

1 に答える 1

5

これは、 LongestCommonSubstringと呼ばれるよく知られた問題です。これは、動的計画法を使用して、で解くことができますO(mn)。ここでm、nは個々の文字列の長さです。ウィキペディアの記事には、わかりやすい擬似コードが含まれています。

于 2012-04-19T16:54:49.513 に答える