Yes, the performance may be better or worse with different algorithms. Agree, Binary search ( https://en.m.wikipedia.org/w/index.php?title=Binary_search&wprov=rarw1) could be a good choice.
sebb <[email protected]> ezt írta (időpont: 2024. aug. 2., P 18:07): > 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] > >
