python - リストのプレフィックスサフィックスの最小リストを取得するアルゴリズムまたは python 実装

Question

単語のリストを使用して、すべての単語が接頭辞と接尾辞の連結になるように、接頭辞と接尾辞の最小リストを与えるアルゴリズムを見つけようとしています。

元 ：

[banano, ananas, applenas, appleno, neo, neas]

=> [bana,anan,e, apple] [as no]

それは可能ですか？

Answer 1

ソリューションは一意に定義されていません。たとえば、言語 [aa, ab, bb] の場合、ソリューションは [a, b] [a, b] または [aa, ab, bb] と空の文字列のいずれかになります。

この問題は、最小文字列カバー問題のインスタンスとして理解できます (各文字列が必須の文字列開始文字で始まり、別の必須文字列終了文字で終わると仮定してください。許可されたカバー辞書は、すべての接頭辞と文字列で構成されます)。入力言語のすべての単語のすべてのサフィックス。

一般的な文字列カバー問題は NP 困難ですが、固定された最大数の文字列 (ここでは 2 つ) のみが任意の入力文字列が与えられると、多項式で解けるようになります。

以下は、最小ストリング カバー問題のソルバーの C++ 実装です。