Suche nach dem längsten Präfix in einem Wörterbuch

Question

Ich implementiere Lempel-Ziv-Komprimierung und eine Frage springt mir in den Sinn.

Gegeben ein 'Wörterbuch' und eine Zeichenkette. Ich möchte in der Lage sein, das längste Präfix der Zeichenfolge zu berechnen, die im Wörterbuch enthalten ist.

das heißt gegeben Strings:

0 : AABB 
1 : ABA 
2 : AAAB 

und die Query-String ‚AABBABA‘ Ich möchte in der Lage sein, die einen Lookup zu tun, das gibt ‚0‘ sollte auf die Länge der in der Zeit linear erfolgen das Präfix.

Als nächstes möchte ich in der Lage sein, das neue Präfix 'AABBAB' dem Wörterbuch in konstanter Zeit hinzuzufügen.

Gibt es einen Standard und einen einfachen Weg/Algorithmus dafür?

Meine ursprüngliche Idee war, einen Standart-N-Wege-Baum mit einer Liste von Zeigern zu bauen und nur diese zu suchen?

Answer 1

Sie beschreiben eine einfache trie Suche, außer dass Sie einen Blattknoten auch dann zurückgeben würden, wenn es zu viele Zeichen gibt.

Nicht sicher, was Sie mit einem n-Wege-Baum denken, aber höchstwahrscheinlich ist es genau das gleiche, da es die offensichtliche Lösung ist: v). Wenn Sie effizienter sein wollen, können Sie verschiedene Arten von Versuchen betrachten.