最小限の長さのすべての一般的な一意の部分文字列 (実際にはパス) を見つける必要がある文字列のリストがあります。例：
/a/b/c
/a/b
/a
/d/e/f
/d/e
/g/h
この入力には、次の結果が必要です。
/a
/d/e
/g/h
ご覧のとおり、一意のプレフィックスを持つ最小限の長さのパス (または部分文字列) が必要です。/a は、/a で始まるすべてのパスの最小部分文字列です。/d/e は、/d/e で始まるすべてのパスの最小部分文字列です。/g/h も同様です。
これの実用的なアプリケーションは、特定のファイルを含むパス ツリーのすべてのルートを見つけて、それらをさらに分析することです。次の例を検討してください。
/a/b/c/index.html
/a/b/index.html
/a/index.html
/d/e/f/index.html
/d/e/index.html
/g/h/index.html
index.html ファイルを含む最上位 (ルートに関して) のパスが必要だとします。その結果、「/a/index.html」、「/d/e/index.html」、「/g/h/index.html」が必要になります。
何か案は？「単純な」最長の共通部分文字列の問題には多くの理論と例がありますが、すべての共通の最長部分文字列を効率的に見つけるための解決策はまだ見つかっていません。
疑似コードを使用したソリューションは高く評価されます。