文字列のリストのすべての共通接頭辞を見つけるための文字列アルゴリズムの提案

Question

文字列のリストの最も長い共通接頭辞を見つけるためにどのようなアルゴリズムをお勧めしますか？

私は、次のような文字列を持っているかもしれません：私は、次の接頭辞を知りたい

Call Mike and schedule meeting. 
Call Lisa 
Call Adam and ask for quote. 
Implement new class for iPhone project 
Implement new class for Rails controller 
Buy groceries 

を：

"Call " 
"Implement new class " 

私はObjective Cのを使用することがありますので、既製ココアソリューションは次のようになりますプラス（必須ではありませんが）。

Answer 1

これは、プレフィックスを考慮する意思の有無によって異なります。

一般的な答えは、すべての文字列をn元のツリーに格納するTrie（おそらくサフィックスツリー）を作成することです。複数の子を持つランクnのすべてのノードを選択することができ、あなたの「プレフィックス」の基準（たとえば、n文字）に応じて、http://en.wikipedia.org/wiki/Trie

参照してください。

繰り返しプレフィックスのリストがあります。

Answer 2

trie（別名プレフィックスツリー）にすべての文字列を挿入できます。次に、複数の子を持つノードが見つかるまで（またはノードに2番目の子を追加するときに文字列の挿入を停止する）まで、ルートからトライをトラバースします。

Answer 3

編集：明確に質問には：文字列

が隣り合う

ソートの最長の共通のプレフィックスを検索して、共通の接頭辞を重複排除、その後の厳格な接頭辞だといういずれかを削除

1. ソート別の

実際には、ステップ（3）のみ、あなたが代わりに並べ替えのトライまたは任意に行うことができた、別のデュープ/プレフィックスだそのいずれかを削除する必要があります。実際には、適切に注釈を付けられたトライですべてを高速化することができます。各ノードに「カウント」を含めると、カウントが2以上のノードが正確に検索されます。 2+のカウント。

並べ替えが組み込まれていれば、隣接する項目を見ることで接頭辞を検出できるので、おそらくそれほど労力はかかりません。

[オリジナルの答え：

ただ、一回限りの操作は、すべての文字列間の最長の共通のプレフィックスを見つけますか？

私は恐らく接頭語の長さの点でそれをするでしょう。擬似コードにおいて、およびNULで終わる文字列を想定：

prefixlen = strlen(first_string); 
foreach string in the list { 
    for (i = 0; i < prefixlen; ++i) { 
     if (string[i] != first_string[i]) { 
      prefixlen = i; 
      break; 
     } 
    } 
    if (prefixlen == 0) break; 
} 

common_prefix = substring(firststring, 0, prefixlen); 

]

Answer 4

1. トライ・データ構造内のすべての文字列を挿入します。
2. ルートからのDFSは、1つ以上のエッジが外に出ている最初のノードを検出します。
3. ルートからステップ2で計算されたノードまでのパスは、すべての文字列セットの最長共通接頭辞を示します。