辞書に含まれる最も長いプレフィックスを見つける

「辞書」と文字列を指定します。私は辞書に含まれている文字列の最長接頭語を計算できるようにしたい。

与えられた文字列：

0 : AABB 
1 : ABA 
2 : AAAB

とクエリ文字列「AABBABA」私は返す検索を行うことができるようにしたいと思います「0」これは、の長さに時間線形に行われる必要があります接頭辞。

次は、新しいプレフィックス 'AABBAB'を一定時間内に辞書に追加したいと考えています。

これを行うための標準的で簡単な方法/アルゴリズムはありますか？

私の元のアイデアは、ポインタのリストでスタンドアールのn-wayツリーを作成し、これを検索することでしたか？

「線形時間」は、辞書検索の複雑さがアルファベットサイズSとは無関係であることを意味しますか？そのサウンドからの「標準的なnウェイ」ツリーは、ノードごとにS個の出力エッジを持つことができます。 – jogojapan

@ jogojapan：あなたは正しいです、私は長さに関して線形を意味します。アルファベットの平均線形の場合定数： –

あなたは余分な文字がある場合でも葉ノードを返すことを除いて、単純なtrieルックアップを記述しています。

あなたはn-wayツリーで何を考えているのかよく分かりませんが、明らかに同じソリューションなので、まったく同じです。より効率的になりたい場合は、さまざまな種類の試行を調べることができます。

2012-04-14 11:54:37 Potatoswatter

単純な検索トライで「新しい接頭辞「AABBAB」」を一定時間内に追加するにはどうすればよいですか？ – jogojapan

@ jogojapan：返されたノードを保持し、末尾を追加するだけで:-) –

確かに、私は、「シンプル・トライ」を、トランジションに個々の文字を持つものとして解釈しました。多分私の間違い。 – jogojapan

答えて