On Fri, 2 Aug 2024 at 15:56, Dávid Szigecsán <[email protected]> wrote:
>
> Hello,
>
> You can do it by calculating the prefix (incrementally) yourself and check
> if it is in the Tree or not.
> So first The prefix you create is just an "A", then "An", and so on until
> your prefix is " Andreas" you will find elements in the Tree by using the
> prefixMap() method.
> And when you create the next prefix "Andreaso", the prefixMap() will return
> an empty map. So you can use the previous generated prefix as the longest
> one.
>
> Example:
> public static <K extends CharSequence, V> K
> findLongestCommonPrefix(Trie<K, V> trie, K value) {
> K longestPrefix = null;
>
> for (int i = 1; i <= value.length(); i++) {
Might be quicker to search by reducing length and exit on first match?
For longer values it might be worth considering searching by binary
chop of the length, though that would complicate the logic.
Just a thought (not tested!)
> K prefix = (K) value.subSequence(0, i);
> if (!trie.prefixMap(prefix).isEmpty()) {
> longestPrefix = prefix;
> } else {
> break;
> }
> }
>
> return longestPrefix;
> }
>
> public static void main(String[] args) {
> Trie<String, String> trie = new PatriciaTrie<>();
> trie.put("Anna", "1");
> trie.put("Anael", "2");
> trie.put("Analu", "3");
> trie.put("Andreas", "4");
> trie.put("Andrea", "5");
> trie.put("Andres", "6");
> trie.put("Anatole", "7");
>
> String value = "Andreasov";
> String longestPrefix = findLongestCommonPrefix(trie, value);
>
> System.out.println("Longest prefix: " + longestPrefix);
> }
>
> Regards,
> David
>
> Erdogan Seref <[email protected]> ezt írta (időpont: 2024. aug. 2., P,
> 16:25):
>
> > Hello,
> >
> > I want to implement a method called findLongestCommonPrefix(Trie<K, V>
> > trie, K value). This method should return the longest key of the trie that
> > is a prefix of value. For example, if the Trie contains 'Anna', 'Anael',
> > 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup of
> > 'Andreasov' would return 'Andreas'. The current method prefixMap does the
> > reverse. How can I implement this method using the methods of the Trie
> > interface?
> >
> > Kind regards
> > Erdogan Seref
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
