文字列のリストを比較するための最良のデータ構造とアルゴリズムは何ですか？

Question

次のルールに一致する可能な限り長い単語のシーケンスを見つけたい：

• 各単語はせいぜい1回使用できます
• すべての単語は文字列です
• 2つの文字列 sa と sb 最後の2文字の場合、連結することができます sa の最初の2文字に一致します sb.

連結の場合、それらの文字を重複させることにより実行されます。例えば：

• sa = "トリノ"
• sb = "novara"
• sa concat sb = "Torinovara"

たとえば、次の入力ファイル「input.txt」があります。

ノバラ

トリノ

Vercelli

ラベンナ

ナポリ

リヴェルノ

メッサニア

noviligure

ローマ

また、上記のルールに従って上記のファイルの出力は次のとおりです。

トリノ

ノバラ

ラベンナ

ナポリ

リボルノ

noviligure

可能な限り長い連結は次のとおりです。

torinovaravennapolivornovilligure

誰かがこれで私を助けてくれませんか？これに最適なデータ構造は何ですか？

Answer 1

これは、指示されたグラフの問題として提示できます - ノードは単語であり、それらが重複する場合（そして最小のオーバーラップが最長の長さを取得するために選択されます）、エッジによって接続され、最高の重量の非交配パスを見つけます。

（実際、実際には、グラフを少し展開して、単語で始まりと終了を処理します。重量の長さの各単語 / 2の間にエッジを持つ「開始ノード」に隣接して、単語、-Overlap +長さの開始+長さの仕上げ / 2、および各単語と「エンディングノード」「長さWord / 2」の間。

https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-in-weighted-graph

Answer 2

私は本当に簡単に始めます。弦の2つのベクトルを作成します。1つは正常にソートされ、1つは最後の2文字でソートされます。 2番目のベクトルのインデックス（intsのベクトル）を作成します。

最も長いものを見つけるために..最初に孤児を削除します。どちらの端に一致しない言葉は何にも一致しません。その後、あなたはaを構築したい 隣人に参加 ツリー、これは、どの単語が互いに届くことができるかを決定する場所です。 2本以上の木がある場合は、最初に最大の木を試してみてください。

今、あなたの仕事は、まれな端を見つけ、それらを他の端に結合し、繰り返すことです。これにより、金色のすべての単語を使用する場合、他の木をスキップする場合、これによりかなり素晴らしいソリューションが得られます。そうでない場合は、これを効率的にするために、たくさんのアルゴリズムになります。

考慮すべき項目：3+ユニークな端がある場合、1つ以上の単語をドロップすることが保証されています。これは、答えを探しながらあなたの試みを剪定するために使用できます。ユニークな終わりを頻繁に再計算します。特定の端の奇数の数は、ドロップする必要があることを確認します（最後に2つの景品を取得します）。セルフマッチが可能な単語を分離し、いつでも最後にそれらを投げることができ、それ以外の場合は数学を悩ませます。小さなマッチングリングを作成できる場合があります。これらを作成するときに孤児にならない限り、これらを自己マッチングの単語のように扱うことができます。これにより、パフォーマンスを素晴らしいものにすることができますが、完璧なソリューションには保証はありません。

検索スペースは注文（n！）数百万の要素のリストを正確な答えを証明するのが難しいかもしれません。もちろん、私は何かを見落とすことができます。