辞書の単語を組み合わせて1つの単語に一致させる

Question

辞書のどれくらいの単語を組み合わせて1つの単語に一致させるかを確認する必要がある問題に取り組んでいます。例えば

：
文字列 "hellogoodsir"、および辞書を考える：{こんにちは、良い、先生、行く、OD、E、L}、ゴールはへのすべての可能な組み合わせを見つけることです文字列を形成する。この場合

、結果が使用3 + 4 = 7ワード、または1 + 1 = 2の組合せをもたらす、ハロー+良い+サー、及びハロー+行く+ OD + SIRあろう。

私が思いついたのは、最初の文字（この例では「h」）で始まるすべての単語を1つのハッシュマップ（startH）に入れ、残りを別のハッシュマップ（endH）に入れるだけです。次にstartHハッシュマップのすべての単語を調べ、 "hellogoodsir"に新しい単語（start + end）が含まれているかどうかを確認します。ここで、endはendHハッシュマップのすべての単語です。そうであれば、一致する単語と等しいかどうかを確認し、使用された各単語の数の値でカウンタをインクリメントします。もしそれが含まれているがそれと等しくないならば、私は新しい単語（すなわちstart + end）を使って同じメソッド（再帰）を呼び出し、最後のハッシュマップの単語を新しい単語に追加して一致。

これは明らかに、多数の単語（および長い文字列が一致する）では非常に遅くなります。この問題を解決するより効率的な方法はありますか？
私が知る限り、これはO（n^2）アルゴリズムですが、これはもっと速くできると確信しています。

Answer 1

あなたの解決策から始めましょう。線形でも二次的な時間でもなく、実際には指数関数的な時間です。 - 溶液は指数時間で

word = "aaa...a" 
dictionary = {"a", "aa", "aaa", ..., "aa...a"} 

ソリューションが可能な各マッチングを通過しているので、そのような指数の数がこの例である：すなわち示す反例。 （既に知られている以前のもの所与）各D[i]がで行われる計算

D[0] = 1 # 
D[i] = sum { D[j] | word.Substring(i,j) is in the dictionary | 0 <= j < i } 

：

しかし、それは再帰式に従うことによって、Dynamic Programmingと、（二次時間最悪の場合）をより効率的に行うことができますO(i) 合計はO(n^2)時間になり、O(n)余分なスペースになります。

クイック注：各D[i]に対するすべて(i,j)ペアの代わりに辞書を繰り返すことにより、あなたはO（k）を達成することができるkが辞書サイズでO(n*k)として終わる各D [i]は、時間。これは潜在的に有効な文字列だけをトラバースすることによって最適化することができますが、上記と同じカウンタの例ではO(n*k)になります。

例：

dictionary = {hello, good, sir, go, od, e, l} 
string = "hellogoodsir" 
D[0] = 1 
D[1] = 0 (no substring h) 
D[2] = 0 (no substring he, d[1] = 0 for e) 
... 
D[5] = 1 (hello is the only valid string in dictionary) 
D[6] = 0 (no dictionary string ending with g) 
D[7] = D[5], because string.substring(5,7)="go" is in dictionary 
D[8] = 0, no substring ending with "oo" 
D[9] = 2: D[7] for "od", and D[5] for "good" 
D[10] = D[11] = 0 (no strings in dictionary ending with "si" or "s") 
D[12] = D[7] = 2 for substring "sir" 

Answer 2

私の提案はprefix treeを使用することです。ルートの下にあるノードは、h,g,s,o,eおよびlとなります。 goとgoodを区別するために、終端文字のノードも必要です。

すべての一致を見つけるには、幅優先探索アプローチを使用します。追跡したい状態は、検索文字列の現在のインデックス、ツリーの現在のノード、これまで使用されている単語のリストです。

状態のリストは、次の状態デキュー、空ではなく、インデックスはノードの子のキーのいずれかと一致するかどうかを確認しながら、初期状態では0、ルート、[]

でなければなりません。その場合は、状態のコピーを変更し、それをエンキューします。また、子のいずれかが終了文字である場合は、同じ状態で単語を州のリストに追加します。

このアルゴリズムではO（n）時間はわかりませんが、はるかに速くする必要があります。