CODEWITHSUNDEEP
c++algorithmdata-structureszip
Martin Kristiansen
Martin Kristiansen

Reputation: 10222

finding the longest prefix contained in a dictionary

I'm implementing Lempel-Ziv compression and a question springs to mind.

Given a 'dictionary' and a string of characters. I want to be able to compute the longest prefix og the string, that is contained in the dictionary.

That is given strings:

0 : AABB
1 : ABA
2 : AAAB

and the query string 'AABBABA' I would like to be able to do the a lookup that returns '0' this should be done in time linear to the length of the prefix.

Next of I would like to be able to add the new prefix 'AABBAB' to the dictionary in constant time.

Is there a standard, and easy way/algorithm for doing this?

My original idea was to build a standart n-way tree with a list of pointers and just search this?

Upvotes: 2

Views: 724

Answers (1)

Potatoswatter
Potatoswatter

Reputation: 137960

You are describing a simple trie lookup, except that you would return a leaf node even when there are excess characters.

Not sure what you're thinking of with an n-way tree, but most likely it's exactly the same, since it's the obvious solution :v) . If you want to be more efficient, you can look into different kinds of tries.

Upvotes: 3

Related Questions