最大等しい文字列サブアレイ

のは、私は2つの文字列を持っているとしましょう：文字列の最大部分配列の最大等しい文字列サブアレイ

"hello" 
"love"

サイズは2：「LO」。ここで

は別の例です：

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

基本的に、どのように私は、最も効率的な方法でこの問題を解決することができますか？

私の考えは以下の通りです：

1つの文字列
のためのすべてのサブアレイが他の文字列のすべてのサブアレイを生成する生成します。
結果は、最大のマッチングサブアレイ

の大きさである。しかし、私は、これはいくつかの悪い-探して力ずくであると考え、すべてのサブアレイ

を比較。どのように私はこれを改善することができますか？

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

EDIT 文字列も必要です。

出典

2012-04-19 David Gomes

これは最も長い共通部分列問題ですか？おそらくこれはhttp://rosettacode.org/wiki/Longest_common_subsequenceがC++がなくても役立つかもしれません！ – ShinTakezou

@ShinTakezouいいえ、それは最も長い共通部分文字列*です - LCSよりずっと簡単です。 – dasblinkenlight

@dasblinkenlightありがとう、私はあまりにも素早く読んでいないと思う – ShinTakezou

これは、Longest Common Substringと呼ばれるよく知られた問題です。 O(mn)で解くことができます。mとnは、動的プログラミングアプローチを使用して、個々の文字列の長さです。 Wikipediaの記事には簡単に従う擬似コードが含まれています。

出典

2012-04-19 16:54:49 dasblinkenlight

しかし、私が見つけたアルゴリズムは、長さを返します、私も文字列が必要です。 –

@ user996056この記事では、さまざまな言語の実装に進む[リンク]（http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring）があります。そこの2番目のC＃実装は文字列を返します。 – dasblinkenlight

それはO（mn）よりはるかに優れています。最適解はO（m + n）であり、これは多数の異なるグラフアルゴリズムによって達成することができる。 – ex0du5

最大等しい文字列サブアレイ

答えて

関連する問題