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++) {
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 <erdogan...@gmail.com> 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
>
