次のルールに一致する単語の可能な限り長いシーケンスを見つけたいと思います。
saであり、の最後の2文字がの最初の2文字と一致するsb場合は連結できます。sasb連結の場合は、それらの文字を重ねて実行します。例えば：
たとえば、次の入力ファイル「input.txt」があります。
novara
トリノ
ベルチェリ
ラヴェンナ
ナポリ
リバノ
メッセニア
ノビリグレ
ローマ
また、上記のルールに従った上記のファイルの出力は次のようになります。
トリノ
novara
ラヴェンナ
ナポリ
リボルノ
ノビリグレ
可能な最長の連結は次のとおりです。
torinovaravennapolivornovilligure
誰かがこれで私を助けてくれますか？これに最適なデータ構造は何でしょうか？
これは有向グラフの問題として提示できます。ノードは単語であり、重なり合う場合はエッジで接続され（そして、最も長い重なりを取得するために最小の重なりが選択されます）、交差しない最大の重みのパスを見つけます。 。
（実際には、グラフを少し拡張して、単語の開始と終了を処理する必要があります。重みの長さword / 2の各単語にエッジを付けて、「開始ノード」に隣接します。単語間、-overlap + length start +長さfinish/2、および各単語と「終了ノード」「長さ単語/ 2」の間。2倍にする方が簡単かもしれません。）
https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph
私は本当に簡単に始めます。文字列の2つのベクトルを作成します。1つは通常どおりに並べ替えられ、もう1つは最後の2文字で並べ替えられます。最初のベクトルの位置を示す2番目のベクトルのインデックス（intのベクトル）を作成します。
最長のものを見つけるには..最初に孤児を削除します。どちらの端も一致しない単語。次に、近隣結合ツリーを構築します。ここで、どの単語が互いに到達できるかを判断します。2つ以上の木がある場合は、最初に最大の木を試してください。
これで、ツリーを使用して、まれな端を見つけ、それらを他の端にバインドして、繰り返すことが仕事になります。これはあなたにかなり良い解決策を与えるはずです、それがあなたの黄金のすべての単語を使うなら、他の木をスキップしてください。そうでない場合は、これを効率的にするための多数のアルゴリズムを使用します。
考慮すべきいくつかの項目：3つ以上の固有の目的がある場合、1つ以上の単語をドロップすることが保証されます。これは、答えを探している間、あなたの試みを取り除くために使用することができます。一意の端を頻繁に再計算します。与えられた端の奇数は、1つを落とさなければならないことを保証します（あなたは端で2つの景品を手に入れます）。自己一致できる単語を分離し、いつでも最後にそれらを投げることができ、そうでなければ数学を台無しにします。あなたは小さな自己一致リングを作成することができるかもしれません、あなたがそれらを作成するときにそれらを孤立させない限り、あなたはこれらを自己一致単語のように扱うことができます。これによりパフォーマンスが素晴らしいものになりますが、完璧なソリューションを保証するものではありません。
検索スペースはorder（N！）です。何百万もの要素のリストは、正確な答えを証明するのが難しい場合があります。もちろん、私は何かを見落としている可能性があります。